DFS-Recall2

发表于 分类于 ，

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

算法描述

​ 首先要再网格中找到起点，遍历整个二维网格，使用网格中的每一个单词跑一遍dfs，找到起点后，每次能向其他三个方向遍历，所以将当前字符置为'.'，然后向每个方向dfs,结束后需要回溯，将之前修改的字符，修改回来，bb[x][y]=word[u]最后返回结果；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int n,m;
    int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1};
    
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size()==0||board[0].size()==0)return false;
        if(word.length()==0)return true;
        m = board.size();
        n = board[0].size();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
               if(dfs(board,i,j,word,0))
                   return true;
        return false;
    }
    
    bool dfs(vector<vector<char>> &bb,int x,int y,string &word,int u){
        if(bb[x][y]!=word[u])return false;
        if(u==word.length()-1)return true;
        
        bb[x][y] = '.';
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<m&&b>=0&&b<n)
                if(dfs(bb,a,b,word,u+1))
                    return true;
        }
        bb[x][y]=word[u];
        return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int m,n;
    int[] dx = {-1,0,1,0};
    int[] dy = {0,-1,0,1};
    public boolean exist(char[][] board, String word) {
        if(board.length==0||board[0].length==0)return false;
        if(word.length()==0)return true;
        m = board.length;
        n = board[0].length;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(dfs(board,i,j,word,0))
                    return true;
        return false;
    }
    
    public boolean dfs(char[][] bb,int x ,int y,String word,int u){
        if(bb[x][y]!=word.charAt(u))return false;
        if(u==word.length()-1)return true;
        
        bb[x][y] = '.';
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<m&&b>=0&&b<n)
                if(dfs(bb,a,b,word,u+1))
                    return true;
        }
        bb[x][y] = word.charAt(u);
        return false;
    }
}