2 C++ solutions, non-recursion and recursion


  • 0
    K

    2 solutions, non-recursion and recursion. In fact, 2 methods are equivalent.
    non-recursion method using stack

    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if(board.empty()) return false;
            int rows=board.size(),cols=board[0].size();
            int options=4;
            vector<pair<int,int>> offset(options);
            offset[0]=make_pair(0,1);
            offset[1]=make_pair(1,0);
            offset[2]=make_pair(0,-1);
            offset[3]=make_pair(-1,0);
            for(int i=0;i<rows;++i)
                for(int j=0;j<cols;++j)
                {
                    if(board[i][j]!=word[0]) continue;
                    int p=1,option=0;
                    stack<pair<int,int>> stk;
                    stk.push(make_pair(i,j));
                    board[i][j]='*';
                    while(!stk.empty())
                    {
                        if(p==word.size()) return true;
                        int r=stk.top().first,c=stk.top().second;
                        int row,col;
                        while(option<options)
                        {
                            row=r+offset[option].first,col=c+offset[option].second;
                            if(row<rows&&row>=0&&col<cols&&col>=0&&board[row][col]==word[p])
                                break;
                            option++;
                        }
                        if(option<options)
                        {
                            stk.push(make_pair(row,col));
                            board[row][col]='*';
                            option=0;
                            p++;
                        }
                        else
                        {
                            stk.pop();
                            if(p) board[r][c]=word[--p];
                            if(!stk.empty())
                            {
                                if(r==stk.top().first)
                                    option=2-c+stk.top().second;
                                else
                                    option=3-r+stk.top().first;
                            }
                        }
                    }
                }
                return false;
        }
    };
    

    recursion method

    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if(board.empty()) 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(IsFound(board,m,n,i,j,word,0))
                        return true;
            return false;
        }
        bool IsFound(vector<vector<char>>& board,int m,int n,int r,int c,string& word,int p)
        {
            if(p==word.size()) return true;
            if(r<0||r>=m||c<0||c>=n||word[p]!=board[r][c]) return false;
            char t=board[r][c];
            board[r][c]='0';
            if(IsFound(board,m,n,r+1,c,word,p+1)||IsFound(board,m,n,r-1,c,word,p+1)||IsFound(board,m,n,r,c+1,word,p+1)||IsFound(board,m,n,r,c-1,word,p+1))
                return true;
            board[r][c]=t;
            return false;
        }
    };

Log in to reply
 

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