[LeetCode] 0139. Problema de ruptura de palabras

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

dada una cuerda s y un diccionario de cuerdas palabraDict, devolver verdadero si s se puede segmentar en una secuencia separada por espacios de una o más palabras del diccionario.

Nota que la misma palabra en el diccionario pueda reutilizarse varias veces en la segmentación.

Ejemplo 1:

Aporte: s = "leetcode", wordDict = ["leet","código"]
Producción: verdadero
Explicación: Devuelve verdadero porque "leetcode" se puede segmentar como "leetcode".

Ejemplo 2:

Aporte: s = "manzanapenmanzana", wordDict = ["manzana","pluma"]
Producción: verdadero
Explicación: Devuelve verdadero porque "applepenapple" se puede segmentar como "apple pen apple". Tenga en cuenta que puede reutilizar una palabra del diccionario.

Ejemplo 3:

Aporte: s = "gatos y perros", wordDict = ["gatos","perros","arena","y","gato"]
Producción: FALSO

Restricciones:

1 <= s.longitud <= 300
1 <= palabraDict.longitud <= 1000
1 <= palabraDict[i].longitud <= 20
s y palabraDict[i] constan únicamente de letras inglesas minúsculas.
Todas las cuerdas de palabraDict son único.

Pitón

				
					# Intenta complejidad de tiempo #: O(n^2 + m*k) Complejidad de espacio #: O(n + m*k) al escribir import List clase TrieNode: def __init__(self): self.isWord = False self.children = {} clase Solución: def wordBreak(self, s: str, wordDict: List[str]) -> bool: root = TrieNode() para palabra en wordDict: curr = raíz para c en word: si c no está en curr.children : curr.children[c] = TrieNode() curr = curr.children[c] curr.isWord = True dp = [False] * len(s) para i en rango(len(s)): si i == 0 o dp[i-1]: curr = raíz para j en rango(i, len(s)): c = s[j] si c no está en curr.children: break curr = curr.children[c] si curr. isWord: dp[j] = True return dp[-1] # DP 2 # complejidad del tiempo: O(n^3 +m*k) # complejidad del espacio: O(n+m*k) # al escribir import List clase # Solución: # def wordBreak(self, s: str, wordDict: List[str]) -> bool: # sLen = len(s) # palabras = set(wordDict) # dp = [False] * (sLen + 1) # dp[0] = Verdadero # para i en el rango(1, sLen + 1): # para j en el rango(i): # si dp[j] y s[j:i] en palabras: # dp[i] = True # break # return True # DP 1 # complejidad de tiempo: O(n*m*k) # complejidad de espacio: O(n) # # de escribir lista de importación clase # Solución: # def wordBreak(self, s: str, wordDict : Lista[str]) -> bool: # sLen = len(s) # dp = [False] * sLen # para i en rango(sLen): # para palabra en wordDict: # wordLen = len(palabra) # si i < palabraLen - 1: # continuar # si i == palabraLen - 1 o dp[i-palabraLen]: # si s[i-palabraLen+1:i + 1] == palabra: # dp[i] = True # romper # print(dp) # return dp[sLen-1] # BFS # complejidad de tiempo: O(n^3 + m*k) # complejidad de espacio: O(n+m*k) # # de colecciones importar deque # de escribir importar Lista clase # Solución: # def wordBreak(self, s: str, wordDict: List[str]) -> bool: # palabras = set(wordDict) # cola = deque([0]) # visto = set() # while cola: # inicio = queue.popleft() # si inicio == len(s): # return True # para final en rango(inicio + 1, len(s) + 1): # si final visto: # continuar # si s[inicio:fin] en palabras: # cola.append(fin) # visto.añadir(fin) # return False S = "applepenapple" WordDict = ["apple", "pen"] print(Solución(). palabraBreak(S, WordDict))

Medio

Pitón

Artículos relacionados