Word Search

Q: ¿Cuál es la complejidad temporal de Word Search?

O(m·n·3^L) para un tablero de m × n y una palabra de longitud L : cada celda puede iniciar un camino y, después del primer paso, cada celda tiene como máximo tres vecinos sin visitar. El espacio adicional es O(L) para la recursión, más O(m·n) para una copia del tablero.

MedioBacktracking Grafos

+10

Recibes una cuadrícula de letras board, una lista de cadenas donde board[r][c] es la letra de la fila r, columna c, y una cadena word.

Devuelve true si puedes trazar word: empieza en cualquier celda y avanza cada vez a la celda de arriba, de abajo, de la izquierda o de la derecha, de modo que las celdas que visites formen word en orden, sin usar nunca una celda dos veces. De lo contrario, devuelve false. Se distingue entre mayúsculas y minúsculas.

Función

exist(board: string-array, word: string) → boolean

boardstring-array: la cuadrícula, una cadena de letras por fila
wordstring: la palabra que hay que trazar
Devuelveboolean: si se puede rastrear la palabra a través de celdas contiguas, usando cada una como máximo una vez

Restricciones

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, y todas las filas tienen la misma longitud.
1 ≤ word.length ≤ 20
board y word contienen solo letras inglesas, mayúsculas y minúsculas.

Ejemplos

Entrada: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Salida: true
Explicación: Empieza en la S de la esquina superior izquierda, ve a la derecha hasta la T, baja hasta la O, ve a la derecha hasta la O y la L, y baja hasta la S que está debajo de la L. Ninguna celda se repite.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "POP"
Salida: false
Explicación: El tablero tiene una P. Después de P y O necesitas otra P, y la única es la casilla inicial, que no se puede usar dos veces.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Salida: false
Explicación: Todas las letras de SAND están en el tablero, pero la única A, en la fila 0, columna 2, no toca ninguna S.

Para ir más allá

En lugar de responder sí o no, ¿puedes contar cuántos recorridos distintos de word contiene el tablero?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Tienes que buscar los caminos a través de la cuadrícula. La búsqueda con retroceso va ampliando un camino letra a letra, marcando cada celda mientras el camino la contiene y desmarcándola al retroceder, para que ningún camino reutilice una celda. La búsqueda es exponencial respecto a la longitud de la palabra, algo que permite un tablero de 6 × 6.

Retroceso con una cuadrícula de celdas visitadas

Intuición

Un camino que forma las primeras i letras continúa hacia cualquier vecino que contenga word[i] y no esté en el camino. Si no hay ningún vecino así, es un callejón sin salida y retrocedes.

Desmarcar es lo que hace que esto sea correcto: una celda por la que pasó un callejón sin salida debe quedar libre para el siguiente intento. Con AA / AB y AAA, ambos intentos desde la esquina superior izquierda quedan atascados. Si sus celdas permanecieran marcadas, no se encontraría la respuesta: esquina inferior izquierda, después esquina superior izquierda y después esquina superior derecha.

Después del primer movimiento, cada paso tiene como máximo tres direcciones nuevas, así que la búsqueda puede explorar hasta m·n·3^L caminos. En un tablero de 5 × 5 con A, 8 A y después una B, hace unas 53,000 comprobaciones de celdas antes de responder false.

Algoritmo

Crea una cuadrícula visited, todo en false.
dfs(r, c, i): false si (r, c) está fuera de la cuadrícula, ya se visitó o no es word[i]; true si i es el último índice.
De lo contrario, marca (r, c), prueba con los cuatro vecinos usando i+1, desmárcala y devuelve si alguna búsqueda tuvo éxito.
Devuelve true si dfs(r, c, 0) tiene éxito desde alguna celda.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Búsqueda con retroceso, marcas in situ y poda

Intuición

Mantén la búsqueda, con dos cambios. Marca las celdas en una copia del tablero escribiendo #, y restaura la letra al volver. # nunca coincide con una letra de la palabra, así que la comprobación de letras también rechaza las celdas del camino.

Después, poda. Si la palabra necesita más apariciones de alguna letra de las que hay en el tablero, devuelve false: así se resuelve el tablero con solo A sin buscar. Un camino leído al revés forma la palabra invertida en las mismas celdas, así que buscar la palabra invertida da la misma respuesta. Empieza por el extremo cuya letra sea menos frecuente en el tablero: hay menos celdas desde las que empezar, y los intentos incorrectos fallan de inmediato.

Con la única B en una esquina entre dos C, la búsqueda hacia delante hace unas 35.000 comprobaciones de celdas; al revés, 27. El peor caso sigue siendo O(m·n·3^L).

Algoritmo

Si la palabra necesita más apariciones de alguna letra de las que hay en el tablero, devuelve false.
Si el tablero tiene más copias de word[0] que de la última letra, invierte word.
Copia el tablero en una cuadrícula que puedas modificar.
dfs(r, c, i): falla si la celda no es word[i]; tiene éxito en el último índice; de lo contrario, asígnale #, prueba cada vecino dentro de los límites con i+1, restáurala y devuelve si alguno tuvo éxito.
Devuelve true si dfs tiene éxito desde alguna celda.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Errores comunes y casos límite

No desmarcar una celda después de una rama fallida: AAA en AA / AB da como resultado false.
No marcar en absoluto: el camino vuelve a su última celda, y POP en el tablero de ejemplo devuelve true.
Leer la celda antes de comprobar los límites: en Python, board[-1] es la última fila, así que los caminos dan la vuelta a la cuadrícula.
Comprobar si se ha encontrado la solución solo después de un movimiento: ["A"] con A debe devolver true.
Marcar cambiando entre mayúsculas y minúsculas: en ["aA"], la a marcada se lee como una segunda A, así que aAA da como resultado true.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Word Search?

O(m·n·3^L) para un tablero de m × n y una palabra de longitud L: cada celda puede iniciar un camino y, después del primer paso, cada celda tiene como máximo tres vecinos sin visitar. El espacio adicional es O(L) para la recursión, más O(m·n) para una copia del tablero.

¿Cómo hace la poda que Word Search sea más rápido?

Cuenta primero las letras y devuelve false si el tablero tiene muy pocas de una de ellas. Después busca desde el final con la letra menos frecuente, desde la que pueden empezar menos celdas. Ninguna de las dos comprobaciones cambia el caso peor.

¿Cuál es la diferencia entre Word Search y Word Search II?

Word Search II pregunta qué palabras de una lista aparecen en el tablero. Buscar una vez por palabra repite trabajo, así que la solución habitual coloca las palabras en un trie y recorre el tablero una vez, abandonando un camino cuando ninguna palabra empieza con sus letras.

def exist(board, word):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Salida Esperada

true