C++ | DFS with explanation
Approach\n1. Search the board for the first letter in the word.\n2. When we encouter that letter set index to 0 perform DFS. (index - 0 = first letter of word)\
### Approach\n1. Search the board for the first letter in the word.\n2. When we encouter that letter set index to 0 perform DFS. (index - 0 = first letter of word)\n\t1. Use a visited array to mark the letters we visited to avoid duplicates\n\t2. increment the index to look for the next letter in the word.\n\t3. If we have reached the end of the word return true.\n\t4. Go to the adjacent 4 cells and see if the next letter is true.\n\t5. Each of the adjacent elements will also perform the same process\n\t5. If any of the adjacent cell returns true return true.\n\t6. If none of the neighbours returned true. mark this node as unvisited and return false\n3. If any of the starting letter DFS searches return true the return true\n4. If word was not found return false\n\nNOTE: \n1. Checkbounds function\nThis function checks if the given indices are valid\n2. To iterate adjacent cells we use vector - dirs {0,1},{0,-1},{1,0},{-1,0}\nThese four values will be added to the current index to get new indices.\n```\nclass Solution {\npublic:\n    \n    bool checkBounds(int i,int j,int r,int c){\n        return i>=0 && i<r && j>=0 && j<c;\n    }\n    \n    bool dfs(vector<vector<char>>& board,vector<vector<int>>& visited,string& word,int i,int j,int p,int r,int c){\n        if(visited[i][j]) return false;\n        visited[i][j] = 1;\n        p++;\n        if(p == word.length()) return true;\n        vector<pair<int,int>>dirs = {{0,1},{0,-1},{1,0},{-1,0}};\n        for(auto dir : dirs){\n            int ii = i+dir.first, jj=j+dir.second;\n            if(checkBounds(ii,jj,r,c) && board[ii][jj] == word[p] && dfs(board,visited,word,ii,jj,p,r,c)){\n                return true;\n            }\n        }\n        visited[i][j] = 0;\n        return false;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) {\n        int r = board.size();\n        int c = board[0].size();\n        char s = word[0];\n        vector<vector<int>>visited(r,vector<int>(c));\n        for(int i=0;i<r;i++){\n            for(int j=0;j<c;j++){\n                if(board[i][j] == s && dfs(board,visited,word,i,j,0,r,c)) return true;\n            }\n        }\n        return false;\n    }\n};\n```
[]