EASY CODE WITH COMMENTS || Simple backtracking || dfs based approach
Intuition\nThe idea is to use backtracking and dfs keeping track of the visited cells.\n\n# Approach\n\n- Traverse through each cell \n- check if the current le
# Intuition\nThe idea is to use backtracking and dfs keeping track of the visited cells.\n\n# Approach\n\n- Traverse through each cell \n- check if the current letter matches or not\n- If the current cell matches with the current letter:\n  1. mark the cell visited(\'#\')\n  2. Recursively explore each of the adjacent cells (Reiterate to the first step in the Approach colon)\n  3. If the last letter of the word matches, return 1(*true*)\n\n# Complexity\n- Time complexity:\n    **O**(*m* * *n* * *4^l*)\n\n- Space complexity:\nO(*l*)                \n// For recursion\n\n# Code\n```\nclass Solution {\npublic:\n        vector<pair<int,int>> v={{0,1},{0,-1},{1,0},{-1,0}};\n        string word;\n    int dfs(int x,int y,vector<vector<char>>& board,int pos)\n    {\n        if(pos==word.length()-1)\n        return 1;\n        char temp=board[x][y];\n    //mark the current cell visited\n        board[x][y]=\'#\';\n    //For each of the adjacent cell, call the function recursively\n        for(auto u:v)\n        if(x+u.first>=0&&x+u.first<board.size()&&y+u.second>=0&&y+u.second<board[0].size())\n        {\n            int res=0;\n            if(board[x+u.first][y+u.second]==word[pos+1])\n            res=dfs(x+u.first,y+u.second,board,pos+1);\n        //return true if a word match is found in one of the neighbours\n            if(res==1)\n            return 1;\n        }\n    //mark the current cell unvisited\n        board[x][y]=temp;\n        return 0;\n    }\n\n    bool exist(vector<vector<char>>& board, string word1) {\n        word=word1;\n        vector<int> v(board[0].size(),0);\n        for(int i=0;i<board.size();i++)\n        {\n            for(int j=0;j<board[0].size();j++)\n            {\n                if(board[i][j]==word[0]&&dfs(i,j,board,0))\n                return 1;\n            }\n        }\n        return 0;\n    }\n};\n```\n**PLEASE UPVOTE IF YOU FIND IT USEFUL**\uD83E\uDD7A\uD83E\uDD7A\uD83E\uDD7A\n\n---\n
['Backtracking', 'Depth-First Search', 'C++']