Word Search

Q: Quelle est la complexité temporelle de Word Search ?

O(m·n·3^L) pour un plateau de m × n et un mot de longueur L : chaque cellule peut démarrer un chemin et, après la première étape, chaque cellule a au plus trois voisins non visités. L’espace supplémentaire est de O(L) pour la récursion, plus O(m·n) pour une copie du plateau.

MoyenRetour sur trace Graphes

+10

Tu disposes d’une grille de lettres board, d’une liste de chaînes où board[r][c] est la lettre de la ligne r, colonne c, et d’une chaîne word.

Retourne true si tu peux tracer word : commence sur n’importe quelle cellule et déplace-toi à chaque fois vers la cellule au-dessus, en dessous, à gauche ou à droite, de sorte que les cellules visitées épellent word dans l’ordre, sans jamais utiliser deux fois la même cellule. Sinon, retourne false. Les lettres sont sensibles à la casse.

Fonction

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

boardstring-array: la grille, une chaîne de lettres par ligne
wordstring: le mot à tracer
Renvoieboolean: si le mot peut être suivi à travers des cellules côte à côte, chacune utilisée au plus une fois

Contraintes

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, et chaque ligne a la même longueur.
1 ≤ word.length ≤ 20
board et word ne contiennent que des lettres anglaises, majuscules et minuscules.

Exemples

Entrée: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Sortie: true
Explication: Commencez en haut à gauche, sur S, allez à droite jusqu’à T, descendez jusqu’à O, allez à droite jusqu’à O et L, puis descendez jusqu’au S sous le L. Aucune case ne se répète.

Entrée: board = ["STAR", "POOL", "ENDS"]word = "POP"
Sortie: false
Explication: Le plateau comporte un P. Après P et O, il vous faut un autre P, et le seul disponible est la case de départ, qui ne peut pas être utilisée deux fois.

Entrée: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Sortie: false
Explication: Chaque lettre de SAND se trouve sur le plateau, mais l’unique A, à la ligne 0, colonne 2, ne touche aucun S.

Pour aller plus loin

Au lieu de répondre par oui ou non, peux-tu compter combien de tracés différents de word se trouvent sur le plateau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Tu dois rechercher les chemins dans la grille. Le retour sur trace construit un chemin lettre par lettre, en marquant chaque case tant que le chemin l’occupe et en la démarquant au retour, afin qu’aucun chemin ne réutilise une case. La recherche est exponentielle en fonction de la longueur du mot, ce qu’autorise un plateau de 6 × 6.

Retour arrière avec une grille de cases visitées

Intuition

Un chemin qui forme les i premières lettres se prolonge vers tout voisin contenant word[i] et ne se trouvant pas sur le chemin. S’il n’existe aucun voisin de ce type, c’est une impasse et il faut revenir en arrière.

C’est le dé-marquage qui garantit la justesse : une cellule traversée par une impasse doit être libre pour la tentative suivante. Avec AA / AB et AAA, les deux tentatives depuis le coin supérieur gauche échouent. Si leurs cellules restaient marquées, la réponse — coin inférieur gauche, puis coin supérieur gauche, puis coin supérieur droit — ne serait pas trouvée.

Après le premier déplacement, chaque étape comporte au plus trois nouvelles directions, donc la recherche peut explorer jusqu’à m·n·3^L chemins. Sur un plateau de 5 × 5 composé de A, avec 8 A suivis d’un B, elle effectue environ 53 000 vérifications de cellules avant de répondre false.

Algorithme

Crée une grille visited, entièrement initialisée à false.
dfs(r, c, i) : renvoie false si (r, c) est en dehors de la grille, a déjà été visitée ou ne correspond pas à word[i] ; renvoie true si i est le dernier indice.
Sinon, marque (r, c), essaie les quatre voisins avec i+1, annule son marquage et renvoie si l’un des essais a réussi.
Renvoie true si dfs(r, c, 0) réussit à partir d’une cellule quelconque.

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

Retour sur trace avec marquages en place et élagage

Intuition

Conservez la recherche, avec deux changements. Marquez les cellules sur une copie du plateau en écrivant #, puis restaurez la lettre en revenant en arrière. # ne correspond jamais à une lettre du mot, donc la vérification des lettres rejette également les cellules déjà sur le chemin.

Élaguez ensuite. Si le mot nécessite davantage d’une lettre que le plateau n’en contient, renvoyez false : cela permet de traiter le plateau entièrement composé de A sans lancer de recherche. Un chemin lu à l’envers forme le mot inversé sur les mêmes cellules ; chercher le mot inversé donne donc la même réponse. Commencez par l’extrémité dont la lettre est la plus rare sur le plateau : moins de cellules peuvent servir de point de départ, et les départs incorrects échouent immédiatement.

Avec l’unique B dans un coin, entre deux C, la recherche dans le sens direct effectue environ 35 000 vérifications de cellules ; dans le sens inverse, 27. Le pire des cas reste O(m·n·3^L).

Algorithme

Si le mot nécessite davantage de lettres d'un certain type que le plateau n'en contient, renvoie false.
Si le plateau contient plus d'exemplaires de word[0] que de la dernière lettre, inverse word.
Copie le plateau dans une grille que tu peux modifier.
dfs(r, c, i) : échoue si la cellule n'est pas word[i] ; réussit au dernier indice ; sinon, remplace sa valeur par #, essaie chaque voisin dans les limites avec i+1, restaure sa valeur et renvoie si l'un d'eux a réussi.
Renvoie true si dfs réussit à partir d'une cellule quelconque.

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

Pièges et cas limites

Ne pas retirer le marquage d’une cellule après l’échec d’une branche : AAA sur AA / AB renvoie false.
Ne rien marquer : le chemin revient sur sa dernière cellule, et POP renvoie true sur le plateau d’exemple.
Lire la cellule avant de vérifier les limites : en Python, board[-1] correspond à la dernière ligne, donc les chemins s’enroulent autour de la grille.
Vérifier la réussite uniquement après un déplacement : ["A"] avec A doit renvoyer true.
Marquer en changeant la casse d’une cellule : sur ["aA"], le a marqué est lu comme un deuxième A, donc aAA renvoie true.

Questions fréquentes3

Quelle est la complexité temporelle de Word Search ?

O(m·n·3^L) pour un plateau de m × n et un mot de longueur L : chaque cellule peut démarrer un chemin et, après la première étape, chaque cellule a au plus trois voisins non visités. L’espace supplémentaire est de O(L) pour la récursion, plus O(m·n) pour une copie du plateau.

Comment l’élagage accélère-t-il la recherche de mots ?

Compte d’abord les lettres, et renvoie false si le plateau en contient trop peu d’une. Ensuite, cherche depuis la fin avec la lettre la plus rare, à partir de laquelle moins de cases peuvent commencer. Aucun des deux contrôles ne modifie le pire des cas.

Quelle est la différence entre Word Search et Word Search II ?

Word Search II demande quels mots d’une liste apparaissent sur le plateau. Effectuer une recherche pour chaque mot répète le travail, donc la solution habituelle place les mots dans un trie et parcourt le plateau une seule fois, en abandonnant un chemin lorsqu’aucun mot ne commence par les lettres qu’il contient.

def exist(board, word):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true