Beats100%|| simple backtracking approach ||easy solution||explained code
Intuition\njust like rat in maze problem.\n\n# Approach\njust using backtracking.\n\n# Complexity\n- Time complexity:\nO(m n word.length() back)\n\n- Space comp
# Intuition\njust like rat in maze problem.\n\n# Approach\njust using backtracking.\n\n# Complexity\n- Time complexity:\nO(m* n* word.length() back)\n\n- Space complexity:\nO(m * n)\n\n\n# Code\n```\nclass Solution {\npublic:\n  bool backtrack(vector<vector<char>>& board,string &word,int i,int j,int &m,int &n,int &index, vector<vector<int>>&v){\n       if(index==word.length()){\n            return true;\n        }\n\n        //down\n        if(i+1<m) {\n            if(board[i+1][j]==word[index] && v[i+1][j]==0){\n            v[i+1][j]=1;\n            index++;\n            i=i+1;\n           bool ans=backtrack(board,word,i,j,m,n,index,v);\n           if(ans){\n              return true;\n           }else{\n            v[i][j]=0;\n            index--;\n            i--;\n           }\n        }\n    }\n        //right\n        if(j+1<n) {\n            if(board[i][j+1]==word[index] && v[i][j+1]==0){\n            v[i][j+1]=1;\n            index++;\n            j=j+1;\n            bool ans=backtrack(board,word,i,j,m,n,index,v);\n           if(ans){\n              return true;\n           }else{\n            v[i][j]=0;\n            index--;\n            j--;\n           }\n        }\n  }\n\n        //up\n    if(i-1>=0){\n     if(board[i-1][j]==word[index] && v[i-1][j]==0){\n        v[i-1][j]=1;\n        index++;\n        i=i-1;\n        bool ans=backtrack(board,word,i,j,m,n,index,v);\n           if(ans){\n              return true;\n           }else{\n            v[i][j]=0;\n            index--;\n            i++;\n           }\n    }\n    }\n        //left\n    if(j-1>=0){\n    if(board[i][j-1]==word[index] && v[i][j-1]==0){\n        v[i][j-1]=1;\n        index++;\n        j=j-1;\n      bool ans=backtrack(board,word,i,j,m,n,index,v);\n           if(ans){\n              return true;\n           }else{\n            v[i][j]=0;\n            index--;\n            j++;\n           }\n    }\n}\nreturn false;\n }\n    bool exist(vector<vector<char>>& board, string word) {\n        int m=board.size();\n        int n=board[0].size();\n       int index=0;\n    \n       vector<vector<int>> v(m,vector<int>(n,0)); \n       for(int i=0;i<m;i++){\n        for(int j=0;j<n;j++){\n          if(board[i][j]==word[index]){\n            index++;\n            v[i][j]=1;\n            //function backtrack if true then return true else move until last element\n            bool answer=backtrack(board,word,i,j,m,n,index,v);\n            if(answer){\n            \n                return true;\n            }\n            index--;\n            v[i][j]=0;\n          }\n        }\n       }\nreturn false;\n    }\n};\n```
['Array', 'String', 'Backtracking', 'Recursion', 'Matrix', 'C++']