[Leetcode] 0212. Búsqueda de palabras II

				
					Complejidad de tiempo #: O(M(4*3^(L-1))) Complejidad de espacio #: O(n) desde la clase de importación List Solución: def findWords(self, board: List[List[str]], words : Lista[str]) -> Lista[str]: WORDKEY = "$" trie = {} para palabra en palabras: nodo = trie para letra en palabra: nodo = nodo.setdefault(letra, {}) nodo[WORDKEY] = palabra rowNum = len(tablero) colNum = len(tablero[0]) matchedWords = [] def backtracking(fila, columna, padre): letra = tablero[fila][columna] currNode = padre[letra] wordMatch = currNode. pop(WORDKEY, False) si wordMatch: palabrascoincidentes.append(wordMatch) tablero[fila][columna] = "#" para desplazamientofila, desplazamientocoluna en [(-1, 0), (0, 1), (1, 0) , (0, -1)]: newRow, newCol = row + rowOffset, col + colOffset si ( newRow < 0 o newRow >= rowNum o newCol < 0 o newCol >= colNum ): continuar si no board[newRow][newCol ] en currNode: continuar retrocediendo (newRow, newCol, currNode) tablero[fila][col] = letra si no currNode: padre.pop(letra) para fila en rango(filaNum): para columna en rango(colNum): si tablero [fila][columna] en trie: backtracking(fila, columna, trie) devuelve matchedWords # complejidad de tiempo: O(n*3^l) # complejidad de espacio: O(m) clase TrieNode: def __init__(self, char=" "): self.char = char self.children = {} self.isEnd = False clase Trie: def __init__(self): self.root = TrieNode() def insert(self, word): nodo = self.root para c en palabra: si c no está en nodo.hijos: nodo.hijos[c] = TrieNode() nodo = nodo.hijos.get(c) nodo.isEnd = True def startsWith(self, prefix): nodo = self.root para c en prefijo: si c no está en node.children: devuelve Falso node = node.children[c] devuelve Verdadero def removeChars(self, word): node = self.root childList = [] para c en word: childList.append( [nodo, c]) nodo = nodo.hijos[c] para padre, hijoChar en reversed(childList): objetivo = padre.hijos[hijoChar] si objetivo.hijos: return del padre.hijos[hijoChar] clase Solución: def findWords (self, tablero: Lista[Lista[str]], palabras: Lista[str]) -> Lista[str]: def dfs(trieForWords: Trie, nodo: TrieNode, cuadrícula: Lista[Lista[str]], fila: int, col: int, resultado: List[str], palabra=""): si nodo.isEnd: resultado.append(palabra) nodo.isEnd = False trieForWords.removeChars(palabra) si 0 <= fila < FILA y 0 <= col < COL: char = grid[row][col] child = node.children.get(char) si child no es None: word += char grid[row][col] = None para dR, dC en [ (0, 1), (1, 0), (-1, 0), (0, -1)]: dfs(trieForWords, hijo, cuadrícula, fila + dR, col + dC, resultado, palabra) cuadrícula[fila ][col] = char ROW = len(tablero) COL = len(tablero[0]) trieForWords = Trie() resultado = [] para palabra en palabras: trieForWords.insert(palabra) para r en rango(ROW): para c en rango(COL): dfs(trieForWords, trieForWords.root, tablero, r, c, resultado) devolver resultado tablero = [["o", "a", "a", "n"], ["e" , "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]] palabras = ["juramento", "guisante", "comer", "lluvia"] print(Solution().findWords(tablero, palabras))