Recherche de mots pour leetcode (solution rétrospective)

Titre

Compte tenu d'un m x n Grille de caractères 2D board Et un mot de chaîne word .Si word Existe dans la grille,Retour true ;Sinon,Retour false .

Les mots doivent être en ordre alphabétique,Composé de lettres dans les cellules adjacentes,Parmi eux“Adjacent”Les cellules sont celles qui sont adjacentes horizontalement ou verticalement.Les lettres d'une même cellule ne peuvent pas être réutilisées.

Exemple 1：

Entrée：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Produits：true
Exemple 2：

Entrée：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Produits：true
Exemple 3：

Entrée：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Produits：false
 

Conseils：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board Et word Se compose uniquement de lettres majuscules et minuscules

Source:：Boucle de force（LeetCode）
Liens：https://leetcode.cn/problems/word-search
Le droit d'auteur est la propriété du réseau de saisie.Pour les réimpressions commerciales, veuillez contacter l'autorisation officielle,Reproduction non commerciale Veuillez indiquer la source.

Idées

Parce qu'il y a peu de temps, j'a I eu un problème de labyrinthe , Donc, après avoir terminé la question, , C'est comme marcher dans un labyrinthe d'émerveillement , Mais les conditions ont changé au fur et à mesure que nous avançons .Mais, Ça m'a quand même coûté 2 Plus près 3 Il a fallu une heure pour l'écrire. ！,Ah!,C'est bon.,C'est toujours trop bon pour moi..

Revenons à nos moutons（ La nourriture ne peut pas être une raison pour laquelle je suis paresseux. ）

Tout d'abord,, Que ce soit dans un labyrinthe ou sur ce sujet , Il doit y avoir un point de départ. ,À ce sujet, Si on essaie un par un, , Ça prendra trop de temps. , Donc j'ai d'abord traversé toute la grille ,  Trouvez la position de la lettre qui correspond à la première lettre du mot que vous recherchez ：

 start_pos_li = []  #  Enregistrer la position initiale du mot 
        word_set = set()  #  Toutes les lettres du tableau 
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                word_set.add(board[i][j])
                if board[i][j] == word[0]:
                    start_pos_li.append((i, j))

Lettres trouvées ajoutées à start_pos_liDans cette liste, Facile à trouver plus tard à partir de ces endroits .

Et j'ai aussi mis en place une collection word_set, Enregistrer toutes les lettres qui apparaissent dans la grille , Avant la recherche officielle , Il est possible de faire un simple jugement pour obtenir rapidement des réponses à quelques châtaignes ：

        for s in word:
            if s not in word_set: return False  #  Si une lettre n'est pas dans le tableau, retournez False

Comme indiqué dans le Code, Traverser les mots à trouver , Une lettre qui n'est pas dans la collection est retournée directement False.

Voici comment commencer la recherche formelle

 1. Définissez d'abord une règle de déplacement ：

 # Bouge(Quatre directions)
    def move(self, x, y, direction):
        if direction == 1:
            return (x - 1, y)
        elif direction == 2:
            return (x + 1, y)
        elif direction == 3:
            return (x, y - 1)
        else:
            return (x, y + 1)

1 Ça veut dire monter ,2 Ça veut dire descendre ,3 Pour déplacer à gauche ,4 Pour se déplacer à droite ; Je prends l'axe horizontal ici. yAxe, Axe longitudinal comme xAxe,Alors... Quand on monte et descend x Changement d'axe trouvé , En se déplaçant à gauche et à droite, y Changement d'axe .

2. Commencez à marcher.

a.Définir un“Pile” Pour sauvegarder le chemin parcouru

path = [start]  # Notez le chemin parcouru

En fait, voici une liste ,Mais n'utilisez queappend()Etpop()Méthodes, Il agit comme une pile. .

b. Définir une liste pour enregistrer la direction dans laquelle chaque grille passe

visit_li = [[set() for j in range(n)] for i in range(m)]  #  Notez la position actuelle dans la direction de l'étape suivante 

J'ai utilisé une collection pour stocker , Une grille stocke jusqu'à quatre directions ,En haut, en bas, à gauche et à droite; Ce n'est pas comme marcher dans un labyrinthe. , Dans le labyrinthe de marche, deux valeurs sont utilisées pour représenter ：0 Indique que la grille actuelle n'est pas passée ,1 Indique que le réseau actuel est parti ; Parce que c'est un mot ici. , Il faut une séquence continue , La grille actuelle ne va peut - être pas dans cette direction , Mais de l'autre côté .（ C'est - à - dire prendre des grilles dans différentes directions , Les séquences obtenues sont toutes différentes ）

c.Essai+Retour en arrière

#  Commencez par la lettre de départ. 
        for start in start_pos_li:
            path = [start]  # Notez le chemin parcouru
            visit_li = [[set() for j in range(n)] for i in range(m)]  #  Notez la position actuelle dans la direction de l'étape suivante 
            while path:
                # print(path)
                if len(path) == len(word): return True  #  Tant que le chemin parcouru et la longueur du mot sont les mêmes, c'est fini 
                cur_pos = path[-1]  # Position actuelle(m,n)
                for step in range(4):  #  Explorer les quatre directions séparément 
                    next_pos = self.move(*cur_pos, step)  # La prochaine étape
                    if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][
                        cur_pos[1]] and next_pos not in set(path):  #  La prochaine étape n'a pas été franchie. 
                        if board[next_pos[0]][next_pos[1]] == word[len(path)]:  #  Les lettres de l'étape suivante sont les mêmes que celles requises 
                            path.append(next_pos)  #  Passer à l'étape suivante 
                            visit_li[cur_pos[0]][cur_pos[1]].add(step)  #  Marquer l'emplacement passé 
                            break
                    else:
                        visit_li[cur_pos[0]][cur_pos[1]].add(step)  #  Ça ne marche pas dans cette direction. 
                else:
                    x, y = path.pop()  #  Si vous ne pouvez pas marcher dans les quatre directions, reculez. 
                    visit_li[x][y] = set()  #  En même temps, videz la direction dans laquelle la position a été passée 

Depuis le début, Essayez les quatre directions à tour de rôle , Si le point de marche est la position actuelle , Et continuer à essayer , Si à un moment donné , Ça ne marche pas dans les quatre sens. ,Pour revenir en arrière, Retour à l'étape précédente ; Continuez dans la direction que vous n'avez pas prise la dernière fois. , Prenons par exemple le châtaignier ：

Code source

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        '''
         C'est comme marcher dans un labyrinthe ,Paramètres4 Direction du Mouvement , En même temps, marquez l'endroit où vous marchez. 
        '''

        start_pos_li = []  #  Enregistrer la position initiale du mot 
        word_set = set()  #  Toutes les lettres du tableau 
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                word_set.add(board[i][j])
                if board[i][j] == word[0]:
                    start_pos_li.append((i, j))

        for s in word:
            if s not in word_set: return False  #  Si une lettre n'est pas dans le tableau, retournez False

        #  Commencez par la lettre de départ. 
        for start in start_pos_li:
            path = [start]  # Notez le chemin parcouru
            visit_li = [[set() for j in range(n)] for i in range(m)]  #  Notez la position actuelle dans la direction de l'étape suivante 
            while path:
                # print(path)
                if len(path) == len(word): return True  #  Tant que le chemin parcouru et la longueur du mot sont les mêmes, c'est fini 
                cur_pos = path[-1]  # Position actuelle(m,n)
                for step in range(4):  #  Explorer les quatre directions séparément 
                    next_pos = self.move(*cur_pos, step)  # La prochaine étape
                    if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][
                        cur_pos[1]] and next_pos not in set(path):  #  La prochaine étape n'a pas été franchie. 
                        if board[next_pos[0]][next_pos[1]] == word[len(path)]:  #  Les lettres de l'étape suivante sont les mêmes que celles requises 
                            path.append(next_pos)  #  Passer à l'étape suivante 
                            visit_li[cur_pos[0]][cur_pos[1]].add(step)  #  Marquer l'emplacement passé 
                            break
                    else:
                        visit_li[cur_pos[0]][cur_pos[1]].add(step)  #  Ça ne marche pas dans cette direction. 
                else:
                    x, y = path.pop()  #  Si vous ne pouvez pas marcher dans les quatre directions, reculez. 
                    visit_li[x][y] = set()  #  En même temps, videz la direction dans laquelle la position a été passée 
            # print('*' * 100)
        return False

    # Bouge(Quatre directions)
    def move(self, x, y, direction):
        if direction == 1:
            return (x - 1, y)
        elif direction == 2:
            return (x + 1, y)
        elif direction == 3:
            return (x, y - 1)
        else:
            return (x, y + 1)

Capture d'écran

Mise à jour synchronisée sur le système de blogging personnel：LeetCodeRecherche de mots(Solution rétrospective)