Using DFS and Backtracking to Search for Word in Grid
Intuition\nTo solve this problem, we can utilize a depth-first search (DFS) approach to explore all possible paths in the grid starting from each cell. We will 
# Intuition\nTo solve this problem, we can utilize a depth-first search (DFS) approach to explore all possible paths in the grid starting from each cell. We will recursively search for the word by traversing horizontally and vertically neighboring cells while ensuring that each letter is used only once.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Implement a DFS function that takes the grid, current cell position, current index in the word, and the word itself as parameters.\n2. Within the DFS function, check if the current index equals the length of the word minus 1. If so, and the current cell contains the corresponding letter, return true as we have found the word.\n3. Explore all four neighboring cells (up, down, left, right) from the current cell. If a neighboring cell matches the next character in the word and is not already visited, mark it as visited and recursively call the DFS function with the updated parameters.\n4. Backtrack by unmarking the cell after exploring its neighbors.\n5. Iterate over each cell in the grid and start DFS from each cell, checking if the word can be found.\n# Complexity\n- Time complexity: O(m * n * 4^k), m=rows, n=cols , k=length of word\n   \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(k), \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c++ []\nclass Solution {\n    int dr1[4]={1,-1,0,0};\n    int dr2[4]={0,0,1,-1};\npublic:\n    bool solve(vector<vector<char>>& board,int& row,int& col,int i,int j,string& word,int ind,int n){\n           if(ind==n-1 && word[ind]==board[i][j])return true;\n           for(int d=0;d<4;d++){\n             int x=i+dr1[d],y=j+dr2[d];\n             if(x>=0&&x<row&&y>=0&&y<col && board[x][y]!=\'.\' && board[x][y]==word[ind]){\n                char ch=board[x][y];\n                board[x][y]=\'.\';\n                if(ind==n-1)return true;\n                if(solve(board,row,col,x,y,word,ind+1,n)==true)return true;\n                board[x][y]=ch; \n             }\n           }\n           return false;\n    }\n    bool exist(vector<vector<char>>& board, string word) {\n        int row=board.size(),col=board[0].size(),n=word.size();\n        for(int i=0;i<row;i++){\n            for(int j=0;j<col;j++){\n                if(solve(board,row,col,i,j,word,0,n)==true)return true;\n            }\n        }\n        return false;\n    }\n};\n```\n```java []\nclass Solution {\n    int[] dr1 = {1, -1, 0, 0};\n    int[] dr2 = {0, 0, 1, -1};\n\n    public boolean solve(char[][] board, int row, int col, int i, int j, String word, int ind, int n) {\n        if (ind == n - 1 && word.charAt(ind) == board[i][j]) return true;\n        for (int d = 0; d < 4; d++) {\n            int x = i + dr1[d], y = j + dr2[d];\n            if (x >= 0 && x < row && y >= 0 && y < col && board[x][y] != \'.\' && board[x][y] == word.charAt(ind)) {\n                char ch = board[x][y];\n                board[x][y] = \'.\';\n                if (ind == n - 1) return true;\n                if (solve(board, row, col, x, y, word, ind + 1, n)) return true;\n                board[x][y] = ch;\n            }\n        }\n        return false;\n    }\n\n    public boolean exist(char[][] board, String word) {\n        int row = board.length, col = board[0].length, n = word.length();\n        for (int i = 0; i < row; i++) {\n            for (int j = 0; j < col; j++) {\n                if (solve(board, row, col, i, j, word, 0, n)) return true;\n            }\n        }\n        return false;\n    }\n}\n\n```\n```python3 []\nfrom typing import List\n\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        def solve(i, j, ind):\n            if ind == len(word):\n                return True\n            if i < 0 or i >= row or j < 0 or j >= col or visited[i][j] or board[i][j] != word[ind]:\n                return False\n            visited[i][j] = True\n            if (solve(i+1, j, ind+1) or\n                solve(i-1, j, ind+1) or\n                solve(i, j+1, ind+1) or\n                solve(i, j-1, ind+1)):\n                return True\n            visited[i][j] = False\n            return False\n        \n        row, col = len(board), len(board[0])\n        visited = [[False] * col for _ in range(row)]\n        \n        for i in range(row):\n            for j in range(col):\n                if solve(i, j, 0):\n                    return True\n        return False\n\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/5036fc57-ffc5-401d-9957-fe0111eae363_1712104998.4331253.jpeg)\n\n\n
['Backtracking', 'Depth-First Search', 'Python', 'C++', 'Java', 'Python3']