Word Search

 https://leetcode.com/problems/word-search/

class Solution {
public:
    int x[4]={0,1,-1,0};
    int y[4]={-1,0,0,1};
    bool solve(int i,int j,vector<vector<char>>& board,vector<vector<int>>&vis,int k,string word,int m,int n)
    {
        if(k==word.size())
            return true;
        if(i<0||j<0||i>=m||j>=n)
            return false;
        if(vis[i][j]||word[k]!=board[i][j])
            return false;
        vis[i][j]=1;
        for(int r=0;r<4;r++)
        {
            if(solve(i+x[r],j+y[r],board,vis,k+1,word,m,n))
                return true;
        }
        vis[i][j]=0;
       return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size();
        int n=board[0].size();
        vector<vector<int>>vis(m,vector<int>(n,0));
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(word[0]==board[i][j])
                {
                    int k=0;
                    if(solve(i,j,board,vis,k,word,m,n))
                       return true;
                }
            }
        }
        return false;
    }
};

 

class Solution {
public:
    bool backtrack(vector<vector<char>>& board, string& word, int pos, int i, int j, int r, int c){
        if(i >= r || j >= c || i < 0 || j < 0 || word[pos] != board[i][j])
            return false;
    
        if(pos == word.length()-1)
            return true;
        
        board[i][j] = '#'; // to avoid using of this character again in the backtracking
        if(backtrack(board, word, pos+1, i+1, j, r, c) || backtrack(board, word, pos+1, i-1, j, r, c) || backtrack(board, word, pos+1, i, j+1, r, c) || backtrack(board, word, pos+1, i, j-1, r, c))
            return true;
	
        board[i][j] = word[pos]; // Reassigning the character as backtracking is complete.
        return false;
    }
    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(backtrack(board, word, 0, i, j, board.size(), board[0].size()))
                    return true;
        return false;
    }
};