Word Search

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

El peor caso es O(m·n·3^L) para un tablero de m × n y una palabra de longitud L . Cada una de las m·n celdas puede iniciar un camino y, después del primer paso, cada celda tiene como máximo tres vecinos no visitados que probar. El espacio adicional es O(L) para la recursión, más O(m·n) si copias el tablero para marcarlo.

MedioBacktracking Grafos

+10

Se te da una cuadrícula de letras board, representada como 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 en la cuadrícula: empieza en cualquier celda y, en cada paso, ve a la celda directamente encima, debajo, a la izquierda o a la derecha de la actual, de modo que las celdas que visites formen word en orden. No puedes usar la misma celda dos veces al trazar. De lo contrario, devuelve false. Se distingue entre mayúsculas y minúsculas, así que a y A son diferentes.

Función

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

boardstring-array: la cuadrícula, una cadena de letras por fila
wordstring: la palabra que debes trazar
Devuelveboolean: si la palabra puede rastrearse 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 fila 0, columna 0; después ve a la derecha hasta la T, baja hasta la O, ve a la derecha hasta la segunda O, sigue a la derecha hasta la L y baja hasta la S de la fila 2, columna 3. Son seis celdas diferentes, cada una junto a la anterior.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "POP"
Salida: false
Explicación: El tablero tiene una sola P, en la fila 1, columna 0. Después de P y O necesitas otra P, y la única está en la casilla donde comenzó el camino, que no se puede usar dos veces.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Salida: false
Explicación: Hay todas las letras de SAND en el tablero, pero el camino se interrumpe en el primer paso: la única A está en la fila 0, columna 2, y ninguna de las S la toca.

+23 pruebas ocultas al enviar

Para ir más allá

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

Pistas

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

0 de 3 abiertas

Solución

Ninguna fórmula resuelve esto: tienes que buscar los caminos a través de la cuadrícula. El retroceso lo hace considerando un camino a la vez. Extiendes el camino una letra, marcas cada celda mientras el camino la ocupa y la desmarcas cuando retrocedes, de modo que una celda nunca se reutiliza dentro de un camino, pero queda libre para todos los demás. En el peor de los casos, esta búsqueda es exponencial respecto a la longitud de la palabra, lo cual está bien en un tablero de como máximo 6 × 6. Dos comprobaciones sencillas antes de empezar, contar las letras y empezar por el extremo menos frecuente de la palabra, suelen reducir el trabajo de decenas de miles de pasos a unas pocas docenas.

Retroceso con una cuadrícula visitada

Intuición

Imagina un árbol de decisiones. La primera elección es la celda inicial y debe contener word[0]. Después, cada nodo es un camino que forma las primeras i letras, y sus hijos son los vecinos que contienen word[i] y que aún no están en el camino. Un camino que forma la palabra completa es un éxito. Un camino sin ningún vecino así es un callejón sin salida, y retrocedes para probar la siguiente opción.

Una cuadrícula visited hace cumplir la regla de usar cada celda una sola vez. Marca una celda cuando el camino pasa por ella y desmárcala cuando el camino retrocede. Desmarcarla es lo que permite este retroceso: una celda por la que pasó un callejón sin salida debe quedar libre de nuevo para el siguiente intento. En el tablero AA / AB con la palabra AAA, empezando en la celda superior izquierda, bajar conduce a un callejón sin salida en la celda inferior izquierda (su otro vecino es B), y moverse a la derecha conduce a un callejón sin salida en la celda superior derecha. Si esas celdas permanecieran marcadas, nunca se podría encontrar la respuesta: inferior izquierda, luego superior izquierda y después superior derecha.

Esta es la respuesta estándar, y aquí es correcta y lo bastante rápida. Su costo es el número de caminos que explora. Después del primer movimiento, cada paso tiene como máximo tres direcciones nuevas, así que una palabra de L letras puede implicar del orden de m·n·3^L caminos. Toma un tablero de 5 × 5 lleno de A y la palabra formada por 8 A seguidas de una B. Cada camino de A es un prefijo válido, y la búsqueda los recorre todos antes de descubrir que no existe ninguna B: alrededor de 65,000 comprobaciones de celdas para responder false. Cada letra adicional aproximadamente duplica esa cantidad, por lo que el siguiente enfoque comprueba algunas cosas antes de buscar.

Algoritmo

Crea una cuadrícula visited del tamaño del tablero, con todas las celdas en falso.
Define dfs(r, c, i): devuelve falso si (r, c) está fuera de la cuadrícula, ya está visitado o su letra no es word[i].
Si i es el último índice de word, devuelve verdadero.
Marca (r, c) como visitado, prueba los cuatro vecinos con i+1, después desmárcalo y devuelve si alguno de los vecinos tuvo éxito.
Llama a dfs(r, c, 0) desde cada celda y devuelve verdadero en cuanto una tenga éxito.

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

Retroceso con marcas in situ y poda

Intuición

Mantén la misma búsqueda y haz dos cambios. Primero, marca las celdas en una copia privada del tablero en lugar de en una cuadrícula aparte: sobrescribe una celda con # mientras la ruta la ocupa y vuelve a escribir la letra al retroceder. # nunca es igual a una letra de la palabra, así que la comprobación de letras también descarta las celdas de la ruta, y restaurar la letra es el mismo paso para deshacer que antes.

Segundo, aplica podas antes de buscar. Cuenta las letras. Si la palabra necesita más copias de alguna letra de las que hay en el tablero, la respuesta es false sin hacer ninguna búsqueda. Así se descarta el tablero con solo As y una B, sin ninguna búsqueda, en lugar de hacer unas 65.000 comprobaciones. Empieza por el extremo menos frecuente. Una ruta leída al revés forma la palabra invertida en las mismas celdas, así que puedes buscar la palabra invertida. Si la última letra es menos frecuente en el tablero que la primera, invierte la palabra. Menos celdas pueden iniciar la búsqueda, y la letra menos frecuente descarta los inicios incorrectos en el primer paso en lugar del último.

La segunda regla importa cuando la letra menos frecuente existe, pero está fuera de alcance. Coloca la única B en una esquina cuyos dos vecinos sean C, y busca 8 As y después una B. El recuento de letras pasa. Hacia delante, la búsqueda sigue recorriendo todas las rutas de A, unas 35.000 comprobaciones de celdas. Con la palabra invertida, esta empieza por B, solo una celda puede iniciar la búsqueda, sus vecinos no son A y la búsqueda termina después de unas 30 comprobaciones.

El peor caso sigue siendo O(m·n·3^L): se puede construir un tablero y una palabra donde las letras estén equilibradas y los callejones sin salida aparezcan tarde. La poda no cambia la respuesta ni la cota. Elimina las formas habituales en que la búsqueda simple pierde tiempo, a cambio de una pasada para contar las letras, y la diferencia crece rápidamente con la longitud de la palabra.

Algoritmo

Cuenta cada letra del tablero y de la palabra. Si la palabra necesita más copias 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 de caracteres que puedas modificar.
Define dfs(r, c, i): falla si la celda no es word[i]; tiene éxito si i es el último índice; en caso contrario, establece la celda como #, prueba cada vecino dentro de los límites con i+1, vuelve a poner la letra y devuelve si alguno tuvo éxito.
Ejecuta dfs(r, c, 0) desde cada celda y devuelve true en cuanto uno tenga éxito.

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

La mayoría de las respuestas incorrectas se deben al marcado y a las comprobaciones de límites.

No desmarcar una celda después de una rama fallida. La celda queda bloqueada para todos los caminos posteriores, y en AA / AB la palabra AAA da como resultado false.
No marcar en absoluto. Sin el marcado, el camino puede volver a la celda de la que partió, y POP en el tablero de ejemplo devolvería true.
Leer la celda antes de comprobar los límites. En Python, board[-1] es la última fila, no un error, así que la falta de una comprobación de límites hace que el recorrido vuelva silenciosamente al otro extremo de la cuadrícula.
Comprobar si se encontró la palabra solo después de un movimiento. Una palabra de una letra en un tablero de una sola celda, ["A"] con A, debe devolver true aunque la celda no tenga vecinos.
Marcar con un carácter que pueda ser una letra real. Cambiar entre mayúsculas y minúsculas una celda, por ejemplo, falla en tableros que usan tanto a como A.
Desplazarse en diagonal. Solo cuentan como vecinos las cuatro celdas que comparten un lado.

Preguntas frecuentes4

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

El peor caso es O(m·n·3^L) para un tablero de m × n y una palabra de longitud L. Cada una de las m·n celdas puede iniciar un camino y, después del primer paso, cada celda tiene como máximo tres vecinos no visitados que probar. El espacio adicional es O(L) para la recursión, más O(m·n) si copias el tablero para marcarlo.

¿Por qué desmarcas las casillas en la sopa de letras?

Una marca indica que la celda está en el camino actual. Cuando una rama falla, la celda sale del camino y puede que otra ruta la necesite. Si conservas la marca, las búsquedas posteriores tratarán la celda como usada y podrían pasar por alto un trazado válido. Marca al entrar y desmarca al salir.

¿Cómo hace la poda que la búsqueda de palabras sea más rápida?

Se realizan dos comprobaciones antes de la búsqueda. Si la palabra necesita más cantidad de alguna letra de la que hay en el tablero, puedes devolver false sin buscar. Y como una ruta leída al revés forma la palabra invertida, puedes empezar por el extremo que tenga la letra menos frecuente, lo que reduce la cantidad de celdas iniciales y descarta antes las rutas incorrectas. Ninguna de las dos cambia el peor caso, y la búsqueda sencilla es una solución completa por sí sola. En un tablero de 5 × 5 de A con una palabra que necesita una B que no está, reducen aproximadamente 65 000 comprobaciones de celdas a ninguna.

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

Word Search pregunta por una palabra. Word Search II proporciona una lista de palabras y pregunta cuáles aparecen en el tablero. Ejecutar esta búsqueda una vez por palabra repite mucho trabajo, así que la solución habitual pone todas las palabras en un trie y recorre el tablero una sola vez, abandonando un camino en cuanto ninguna palabra empieza con sus letras.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

true