Leetcode 79. Word Search [C + + / java detailed problem]

「C'est ma participation11Le défi du mois de juin25Oh, mon Dieu.,Voir les détails de l'événement：2021Un dernier défi」. De l'Université des sciences du lac

1、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
Copier le Code

Exemple 2：

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

Exemple 3：

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

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

2、Idées

(Retour en arrière) $O(n^2 3^k)$

Recherche en profondeur,Nous définissons un tel ordre de recherche,C'est - à - dire énumérer d'abord le début d'un mot,Ensuite, énumérez chaque lettre du mot à son tour.Dans ce processus, il est nécessaire de changer la lettre déjà utilisée en une lettre spéciale,Pour éviter la réutilisation des caractères.

Conception de la fonction récursive：

bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y) Copier le Code

uReprésente le mot cible actuellement énuméréwordNouPosition.

x,yEst l'abscisse et l'ordonnée de la grille de caractères 2D actuellement recherchée.

Le processus de recherche est le suivant：

• 1、Énumérez les points de départ de chaque mot dans une grille de caractères 2D.
• 2、À partir de ce point de départ, cherchez des mots autour de vousword,Et Notez qu'à ce moment - là, l'énumération des motswordDeuPosition ( uDe0C'est parti.).
• 3、Si l'emplacement de la recherche actuelle(x,y)Éléments deboard[x][y] == word[u],Continuez à chercher partout.
• 4、Jusqu'à ce qu'il soit énuméré au motwordLa dernière lettre deture,Sinon, retournez àfalse.

Limite récursive：

• 1、Lorsque l'emplacement actuel apparaît dans le processus de rechercheboard[x][y] != word[u] ,Description le chemin actuel est illégal,Retourfalse.
• 2、u == word.size() - 1,Recherche réussie à la fin du mot,Retourtrue.

Détails de la mise en œuvre：

• 1、 Lorsque vous continuez à chercher le niveau suivant ,L'emplacement actuel doit être identifié,Indique qu'une recherche a été effectuée

• 2、Vous pouvez utiliser un tableau offset pour simplifier le Code.

Analyse de la complexité temporelle： Il y a un total de $n^2$ - Oui.,Chaque lettre d'un mot a quatre directions à choisir,Mais comme il n'y a pas de retour en arrière,Donc, à part les initiales,Il n'y a que trois options.Donc la complexité temporelle totale est $O(n^2 3^k)$ .

3、c++Code

class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i = 0; i < board.size(); i++)
for(int j = 0; j < board[i].size(); j++)
if(dfs(board,word,0,i,j)) return true;
return false;
}
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1}; //Tableau de direction
bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y) {
if(board[x][y] != word[u]) return false;
if(u == word.size() - 1) return true;
char t = board[x][y];
board[x][y] = '.';
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
//Sortir de la frontière ou aller à un endroit déjà recherché
if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.') continue;
if(dfs(board,word,u+1,a,b)) return true;
}
board[x][y] = t;
return false;
}
};
Copier le Code

4、javaCode

class Solution {
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++)
for(int j = 0; j < board[i].length; j++)
if(dfs(board,word,0,i,j)) return true;
return false;
}
int[] dx = new int[]{-1,0,1,0}, dy = new int[]{0,1,0,-1};
boolean dfs(char[][] board, String word,int u,int x,int y) {
if(board[x][y] != word.charAt(u)) return false;
if(u == word.length() - 1) return true;
char t = board[x][y];
board[x][y] = '.';
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= board.length|| b < 0 || b >= board[0].length || board[a][b] == '.') continue;
if(dfs(board,word,u+1,a,b)) return true;
}
board[x][y] = t;
return false;
}
}
Copier le Code

Lien vers la question originale：79. Recherche de mots