[recommend for beginners]clean C++ implementation with detailed explanation


  • 3
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if(board.size()==0)  return false;
            int m=board.size(), n=board[0].size();
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(help(board, i, j, 0, word))  return true;
                }
            }
            return false;
        }
        
        bool help(vector<vector<char>>& board, int i, int j, int len, string word){
            if(len==word.size())   return true;
            if(i<0 || j<0 || i>=board.size() || j>=board[0].size())  return false;
            if(board[i][j]!=word[len] || board[i][j]=='*')  return false;
            char ch=board[i][j];
            board[i][j]='*';
            bool result= help(board, i+1, j, len+1, word) ||
                         help(board, i-1, j, len+1, word) ||
                         help(board, i, j+1, len+1, word) ||
                         help(board, i, j-1, len+1, word);
            board[i][j]=ch;
            return result;
        }
    };

  • 1
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            int m=board.size(), n=board[0].size();
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(help(board, word, i, j, 0))
                        return true;
                }
            }
            return false;
        }
        
        bool help(vector<vector<char>>& board, string word, int i, int j, int pos){
            if(i<0 || j<0 || i>=board.size() || j>=board[0].size() || board[i][j]!=word[pos] || board[i][j]=='*')  return false;
            char temp=board[i][j];
            board[i][j]='*';
            if(pos==word.size()-1)  return true;
            bool flag=
                   help(board, word, i+1, j, pos+1) || 
                   help(board, word, i-1, j, pos+1) ||
                   help(board, word, i, j+1, pos+1) ||
                   help(board, word, i, j-1, pos+1);
            board[i][j]=temp;
            return flag;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.