[Leetcode] 0079. Búsqueda 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

dado un xn cuadrícula de caracteres junta y una cuerda palabra, devolver verdadero si palabra existe en la red.

La palabra puede construirse a partir de letras de celdas adyacentes secuencialmente, donde las celdas adyacentes están adyacentes horizontal o verticalmente. La misma celda de letra no puede usarse más de una vez.

Ejemplo 1:

Aporte: tablero = [["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E" ","E"]], palabra = "ABCCED"
Producción: verdadero

Ejemplo 2:

Aporte: tablero = [["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E" ","E"]], palabra = "VER"
Producción: verdadero

Ejemplo 3:

Aporte: tablero = [["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E" ","E"]], palabra = "ABCB"
Producción: FALSO

Restricciones:

m == longitud del tablero
n = tablero[i].longitud
1 <= m, n <= 6
1 <= longitud de palabra <= 15
junta y palabra Consta únicamente de letras mayúsculas y minúsculas en inglés.

Hacer un seguimiento: ¿Podrías utilizar la poda de búsqueda para hacer que tu solución sea más rápida con un mayor número de resultados? junta?

Tabla de contenido

Pitón

				
					Complejidad de tiempo #: O(c*3^l) Complejidad de espacio #: O(l) desde la clase de importación List Solución: def exist(self, board: List[List[str]], word: str) -> bool: def backtrack(suffix: str, r: int, c: int): si len(suffix) == 0: devuelve Verdadero si no (0 <= r < ROW y 0 <= c < COL) o suffix[0] ! = board[r][c]: devuelve Falso resultado = Falso originalChar = board[r][c] board[r][c] = "#" para dr,dc en ([1,0],[0,1 ],[-1,0],[0,-1]): resultado = backtrack(suffix[1:], r+dr, c+dc) if resultado: break board[r][c] = originalChar return resultado FILA = len(tablero) COL = len(tablero[0]) para fila en rango(FILA): para columna en rango(COL): si backtrack(palabra, fila, columna): devuelve Verdadero devuelve Falso tablero = [[" A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E" ]] palabra = "ABCCED" print(Solución().exist(tablero, palabra))

Pitón

Artículos relacionados