Word Search

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

Le pire cas est O(m·n·3^L) pour un plateau de m × n et un mot de longueur L . Chacune des m·n cellules peut être le point de départ d’un chemin et, après la première étape, chaque cellule a au plus trois voisins non visités à essayer. L’espace supplémentaire est de O(L) pour la récursion, plus O(m·n) si tu copies le plateau pour le marquer.

MoyenRetour sur trace Graphes

+10

On vous donne une grille de lettres board, sous la forme d’une liste de chaînes où board[r][c] est la lettre de la ligne r, colonne c, ainsi qu’une chaîne word.

Renvoyez true si vous pouvez tracer word sur la grille : commencez sur n’importe quelle case, puis déplacez-vous à chaque étape vers la case directement au-dessus, en dessous, à gauche ou à droite de la case actuelle, de sorte que les cases visitées épellent word dans l’ordre. Un tracé ne peut pas utiliser deux fois la même case. Sinon, renvoyez false. La casse des lettres est prise en compte : a et A sont donc différentes.

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 retracé à 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: Commence sur le S à la ligne 0, colonne 0, puis va à droite jusqu’au T, descends jusqu’au O, va à droite jusqu’au deuxième O, va à droite jusqu’au L, puis descends jusqu’au S de la ligne 2, colonne 3. Cela fait six cellules différentes, chacune adjacente à la précédente.

Entrée: board = ["STAR", "POOL", "ENDS"]word = "POP"
Sortie: false
Explication: Le plateau comporte un seul P, à la ligne 1, colonne 0. Après P et O, il vous faut un autre P, et le seul disponible est la case où le chemin a commencé, qui ne peut pas être utilisée deux fois.

Entrée: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Sortie: false
Explication: Toutes les lettres de SAND sont sur le plateau, mais le chemin se rompt dès la première étape : le seul A se trouve à la ligne 0, colonne 2, et aucun des S ne le touche.

+23 tests cachés à la soumission

Pour aller plus loin

Au lieu de répondre par oui ou par 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

Aucune formule ne permet de répondre à cette question : il faut rechercher les chemins dans la grille. Le retour sur trace explore un chemin à la fois. Tu prolonges le chemin d’une lettre, tu marques chaque cellule tant que le chemin l’occupe, puis tu la démarques lorsque tu reviens en arrière : ainsi, une cellule n’est jamais réutilisée dans un même chemin, mais reste disponible pour tous les autres chemins. Dans le pire des cas, cette recherche est exponentielle en fonction de la longueur du mot, ce qui convient pour un plateau de 6 × 6 au maximum. Deux vérifications simples avant de commencer — compter les lettres et partir de l’extrémité la plus rare du mot — réduisent souvent le travail de dizaines de milliers d’étapes à quelques dizaines.

Retour sur trace avec une grille de cases visitées

Intuition

Imagine un arbre de décision. Le premier choix est la cellule de départ, et elle doit contenir word[0]. Ensuite, chaque nœud est un chemin qui forme les i premières lettres, et ses enfants sont les voisins qui contiennent word[i] et ne font pas encore partie du chemin. Un chemin qui forme le mot entier est une réussite. Un chemin sans voisin de ce type est une impasse, et tu reviens en arrière pour essayer le choix suivant.

Une grille visited applique la règle d’utilisation unique. Marque une cellule lorsque le chemin y passe et démarque-la lorsque le chemin en repart. C’est ce démarquage qui permet le retour sur trace : une cellule traversée par une impasse doit être de nouveau libre pour la tentative suivante. Sur le plateau AA / AB avec le mot AAA, en partant de la cellule en haut à gauche, descendre mène à une impasse en bas à gauche (son autre voisin est B), et aller à droite mène à une impasse en haut à droite. Si ces cellules restaient marquées, la réponse — bas à gauche, puis haut à gauche, puis haut à droite — ne pourrait jamais être trouvée.

C’est la solution classique, et elle est correcte et suffisamment rapide ici. Son coût correspond au nombre de chemins qu’elle explore. Après le premier déplacement, chaque étape offre au maximum trois nouvelles directions, donc un mot de L lettres peut représenter de l’ordre de m·n·3^L chemins. Prenons un plateau de 5 × 5 rempli de A et le mot composé de 8 A suivis d’un B. Chaque chemin constitué de A est un préfixe valide, et la recherche les parcourt tous avant de découvrir qu’il n’existe aucun B : environ 65,000 vérifications de cellules pour répondre false. Chaque lettre supplémentaire double approximativement ce nombre, d’où l’intérêt de l’approche suivante, qui vérifie quelques éléments avant de lancer la recherche.

Algorithme

Crée une grille visited de la taille du plateau, avec toutes les valeurs à false.
Définis dfs(r, c, i) : renvoie false si (r, c) est en dehors de la grille, a déjà été visité ou si sa lettre n'est pas word[i].
Si i est le dernier indice de word, renvoie true.
Marque (r, c) comme visité, essaie les quatre voisins avec i+1, puis marque à nouveau cette case comme non visitée et renvoie si l'un des voisins a réussi.
Appelle dfs(r, c, 0) depuis chaque cellule et renvoie true dès que l'un des appels réussit.

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

Conserve la même recherche et apporte deux changements. D’abord, marque les cases sur une copie privée de la grille au lieu d’utiliser une grille distincte : remplace une case par # tant qu’elle fait partie du chemin, puis réécris la lettre lorsque tu reviens en arrière. # n’est jamais égal à une lettre du mot ; la vérification de la lettre rejette donc aussi les cases du chemin, et la restauration fait partie de la même étape d’annulation qu’auparavant.

Ensuite, applique des élagages avant de lancer la recherche. Compte les lettres. Si le mot nécessite davantage d’exemplaires d’une lettre que la grille n’en contient, la réponse est false sans aucune recherche. Cela permet de traiter le cas d’une grille remplie de A avec 8 A et un B sans effectuer la moindre recherche, au lieu d’environ 65 000 vérifications. Commence par l’extrémité la plus rare. Un chemin parcouru à l’envers forme le mot inversé sur les mêmes cases ; tu peux donc chercher le mot inversé à la place. Si la dernière lettre est plus rare sur la grille que la première, inverse le mot. Moins de cases peuvent lancer une recherche, et la lettre rare élimine les mauvais départs dès la première étape au lieu de la dernière.

La deuxième règle est importante lorsque la lettre rare existe, mais qu’elle est inaccessible. Place l’unique B dans un coin dont les deux voisines sont des C, puis cherche 8 A suivis d’un B. Le comptage des lettres réussit. En partant du début, la recherche parcourt toujours tous les chemins de A, soit environ 35 000 vérifications de cases. En inversant le mot, celui-ci commence par B ; une seule case peut servir de départ, ses voisines ne sont pas des A, et la recherche s’arrête après environ 30 vérifications.

Le pire cas reste O(m·n·3^L) : on peut construire une grille et un mot où les lettres sont équilibrées et où les impasses surviennent tard. L’élagage ne change ni la réponse ni la complexité. Il élimine les causes fréquentes de perte de temps de la recherche simple, au prix d’un passage pour compter les lettres, et l’écart augmente rapidement avec la longueur du mot.

Algorithme

Compte chaque lettre sur le plateau et dans le mot. Si le mot nécessite davantage d'une lettre que le plateau n'en contient, renvoie false.
Si le plateau contient plus d'occurrences de word[0] que de la dernière lettre, inverse word.
Copie le plateau dans une grille de caractères que tu peux modifier.
Définis dfs(r, c, i) : échoue si la cellule n'est pas word[i] ; réussit si i est le dernier indice ; sinon, remplace la cellule par #, essaie chaque voisin dans les limites avec i+1, remets la lettre, puis renvoie si l'un des essais a réussi.
Lance dfs(r, c, 0) depuis chaque cellule et renvoie true dès que l'un des essais réussit.

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

La plupart des mauvaises réponses viennent du marquage et des vérifications des limites.

Ne pas démarquer une cellule après l’échec d’une branche. La cellule reste bloquée pour tous les chemins suivants, et sur AA / AB, le mot AAA est considéré comme absent.
Ne pas marquer du tout. Sans cela, le chemin peut revenir sur la cellule d’où il vient, et POP renverrait true sur le plateau d’exemple.
Lire la cellule avant de vérifier les limites. En Python, board[-1] est la dernière ligne, et non une erreur ; sans vérification des limites, on boucle discrètement autour de la grille.
Ne vérifier la réussite qu’après un déplacement. Un mot d’une seule lettre sur un plateau d’une seule cellule, ["A"] avec A, doit renvoyer true, même si la cellule n’a aucun voisin.
Marquer avec un caractère qui peut être une vraie lettre. Modifier la casse d’une cellule, par exemple, échoue sur les plateaux qui utilisent à la fois a et A.
Se déplacer en diagonale. Seules les quatre cellules qui partagent un côté comptent comme voisines.

Questions fréquentes4

Quelle est la complexité temporelle de Word Search ?

Le pire cas est O(m·n·3^L) pour un plateau de m × n et un mot de longueur L. Chacune des m·n cellules peut être le point de départ d’un chemin et, après la première étape, chaque cellule a au plus trois voisins non visités à essayer. L’espace supplémentaire est de O(L) pour la récursion, plus O(m·n) si tu copies le plateau pour le marquer.

Pourquoi décocher des cases dans une recherche de mots ?

Une marque signifie que la cellule se trouve sur le chemin actuel. Lorsqu’une branche échoue, la cellule quitte le chemin et un autre chemin peut en avoir besoin. Si tu conserves la marque, les recherches ultérieures considéreront la cellule comme déjà utilisée et risqueront de manquer une tracée valide. Marque à l’entrée, démarque à la sortie.

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

Deux vérifications sont effectuées avant la recherche. Si le mot nécessite davantage de lettres que le plateau n’en contient, tu peux renvoyer false sans effectuer la recherche. Et comme un chemin lu à l’envers épelle le mot inversé, tu peux commencer par l’une ou l’autre extrémité, celle qui contient la lettre la plus rare, ce qui réduit le nombre de cases de départ et permet d’écarter plus tôt les mauvais chemins. Aucun de ces changements ne modifie le pire cas, et la recherche simple constitue à elle seule une réponse complète. Sur un plateau de 5 × 5 composé de A, avec un mot qui nécessite un B absent, ils ramènent environ 65 000 vérifications de cases à aucune.

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

Word Search porte sur un seul mot. Word Search II fournit une liste de mots et demande lesquels apparaissent sur le plateau. Effectuer cette recherche une fois par mot répète beaucoup de travail ; la solution habituelle consiste donc à placer tous les mots dans un trie et à parcourir le plateau une seule fois, en abandonnant un chemin dès qu’aucun mot ne commence par les lettres qu’il contient.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

true