79. Word Search

╰+攻爆jí腚メ 2021-10-29 15:56 213阅读 0赞

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,  
Given board =

[
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]

word = `"ABCCED"`, -> returns `true`,  
word = `"SEE"`, -> returns `true`,  
word = `"ABCB"`, -> returns `false`.

思路：DFS。对Board的每一个字母，如果其正好等于word\[0\]，就以此作为help函数的入口，调用help函数。使用pos数组记录字符是否已经被使用。解释一下help函数各个参数的意义：help(vector<vector<char>> &board,vector<vector<bool>> &pos,string &word,int cur,int x,int y) ,pos记录字符是否被使用，如果pos\[i\]\[j\]=true,表示board\[i\]\[j\]字符已经被使用。word是最终要匹配的单词。cur表示当前已经处理了几个字符。x,y表示前一个字符的位置。如果cur等于字符串word的长度，表示已经找到了单词word，直接返回true。然后尝试从四个方向中的合法位置中去匹配字符word\[cur\],能够匹配就递归调用help(board,pos,word,cur+1,pos\_x,pos\_y)。如果递归函数返回true,表示找到了单词word,返回true。如果一直找不到word,就返回false。

1.      class Solution {
        private:
            int dir[4][2] = {
                 {-1, 0}, {
                 1, 0}, {
                 0, -1}, {
                 0, 1}};  
        public:
            bool help(vector<vector<char>> &board,vector<vector<bool>> &pos,string &word,int cur,int x,int y){
                if(cur==word.length())
                    return true;
                for(int i=0;i<4;i++){
                    int pos_x=x+dir[i][0];
                    int pos_y=y+dir[i][1];
                    if(pos_x>=0&&pos_x<board.size()&&pos_y>=0&&pos_y<board[0].size()&&!pos[pos_x][pos_y]&&board[pos_x][pos_y]==word[cur]){
                        pos[pos_x][pos_y]=true;
                        if(help(board,pos,word,cur+1,pos_x,pos_y))
                            return true;
                        pos[pos_x][pos_y]=false;
                    }
                }
                return false;
            }
            bool exist(vector<vector<char>>& board, string word) {
                if(word.length()==0)
                    return true;
                int m=board.size();
                int n=board[0].size();
                vector<vector<bool>>pos(m,vector<bool>(n,false));
                for(int i=0;i<m;i++){
                    for(int j=0;j<n;j++){
                        if(word[0]==board[i][j]){
                            pos[i][j]=true;
                            if(help(board,pos,word,1,i,j))
                                return true;
                            pos[i][j]=false;
                        }
                    }
                }
                return false;
            }
        };

转载于:https://www.cnblogs.com/zhoudayang/p/5071716.html