Subsecuencia de Grupos Adyacentes Desiguales más Larga II
Se te da un arreglo de cadenas words y un arreglo groups, ambos arreglos tienen longitud n.
La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los caracteres correspondientes son diferentes.
Necesitas seleccionar la subsecuencia más larga de un arreglo de índices tal que para la subsecuencia denotada como con longitud , se cumple lo siguiente:
- Para índices adyacentes en la subsecuencia, sus grupos correspondientes son desiguales, es decir, para cada
jdonde0 < j + 1 < k. - y son iguales en longitud, y la distancia de Hamming entre ellos es
1, donde0 < j + 1 < k, para todos los índices en la subsecuencia.
Devuelve un arreglo de cadenas que contenga las palabras correspondientes a los índices (en orden) en la subsecuencia seleccionada. Si hay múltiples respuestas, devuelve cualquiera de ellas.
Nota: las cadenas en words pueden tener longitudes desiguales.
Ejemplos
Ejemplo 1:
Input: words = ["bab","dab","cab"], groups = [1,2,2]
Output: ["bab","cab"]
Explicación: Una subsecuencia que se puede seleccionar es [0,2].
- groups[0] != groups[2]
- words[0].length == words[2].length, y la distancia de Hamming entre ellos es 1.
Por lo tanto, una respuesta válida es [words[0],words[2]] = ["bab","cab"].
Otra subsecuencia que se puede seleccionar es [0,1].
- groups[0] != groups[1]
- words[0].length == words[1].length, y la distancia de Hamming entre ellos es 1.
Por lo tanto, otra respuesta válida es [words[0],words[1]] = ["bab","dab"].
Se puede demostrar que la longitud de la subsecuencia más larga de índices que satisface las condiciones es 2.
Ejemplo 2:
Input: words = ["a","b","c","d"], groups = [1,2,3,4]
Output: ["a","b","c","d"]
Explicación: Podemos seleccionar la subsecuencia [0,1,2,3].
Satisface ambas condiciones.
Por lo tanto, la respuesta es [words[0],words[1],words[2],words[3]] = ["a","b","c","d"].
Tiene la longitud más larga entre todas las subsecuencias de índices que satisfacen las condiciones.
Por lo tanto, es la única respuesta.
Soluciones
Python
class Solution:
def getWordsInLongestSubsequence(self,words, groups):
n = len(words)
lis = [1] * n
parent = [-1] * n
lis_len = 1
lis_end = 0
def hammingDistance(s1, s2):
if len(s1) != len(s2):
return float('inf')
return sum(c1 != c2 for c1, c2 in zip(s1, s2))
for i in range(n):
for j in range(i + 1, n):
if (groups[i] != groups[j] and
len(words[i]) == len(words[j]) and
hammingDistance(words[i], words[j]) == 1 and
lis[i] + 1 > lis[j]):
lis[j] = lis[i] + 1
parent[j] = i
if lis[j] > lis_len:
lis_len = lis[j]
lis_end = j
ans = []
cur = lis_end
while cur != -1:
ans.append(words[cur])
cur = parent[cur]
ans.reverse()
return ans