✅96.45%🔥Easy Solution🔥with explanation🔥
Intuition\n#### The problem can be solved by traversing the grid and performing a depth-first search (DFS) for each possible starting position. At each cell, we
# Intuition\n#### The problem can be solved by traversing the grid and performing a depth-first search (DFS) for each possible starting position. At each cell, we check if the current character matches the corresponding character of the word. If it does, we explore all four directions (up, down, left, right) recursively until we find the complete word or exhaust all possibilities.\n---\n\n# Approach\n#### 1. Implement a recursive function `backtrack` that takes the current position `(i, j)` in the grid and the current index `k` of the word.\n#### 2.Base cases:\n - ##### If `k` equals the length of the word, return `True`, indicating that the word has been found.\n - ##### If the current position `(i, j)` is out of the grid boundaries or the character at `(i, j)` does not match the character at index `k` of the word, return `False`.\n#### 3.Mark the current cell as visited by changing its value or marking it as empty.\n#### 4. Recursively explore all four directions (up, down, left, right) by calling `backtrack` with updated positions `(i+1, j), (i-1, j), (i, j+1), and (i, j-1)`.\n#### 5.If any recursive call returns `True`, indicating that the word has been found, return `True`.\n#### 6. If none of the recursive calls returns `True`, reset the current cell to its original value and return `False`.\n#### 7. Iterate through all cells in the grid and call the `backtrack` function for each cell. If any call returns `True`, return `True`, indicating that the word exists in the grid. Otherwise, return `False`.\n\n---\n\n# Complexity\n- ## Time complexity:\n#### $$O(m * n * 4^l)$$, where m and n are the dimensions of the grid and l is the length of the word. The $$4^l$$ factor represents the maximum number of recursive calls we may have to make for each starting cell.\n\n- ## Space complexity:\n#### $$O(l)$$, where l is the length of the word. The space complexity is primarily due to the recursive stack depth during the DFS traversal.\n\n---\n# Code\n\n```python []\nclass Solution:\n    def exist(self, board, word):\n        def backtrack(i, j, k):\n            if k == len(word):\n                return True\n            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:\n                return False\n            \n            temp = board[i][j]\n            board[i][j] = \'\'\n            \n            if backtrack(i+1, j, k+1) or backtrack(i-1, j, k+1) or backtrack(i, j+1, k+1) or backtrack(i, j-1, k+1):\n                return True\n            \n            board[i][j] = temp\n            return False\n        \n        for i in range(len(board)):\n            for j in range(len(board[0])):\n                if backtrack(i, j, 0):\n                    return True\n        return False\n```\n```C++ []\nclass Solution {\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        int m = board.size();\n        int n = board[0].size();\n        \n        function<bool(int, int, int)> backtrack = [&](int i, int j, int k) {\n            if (k == word.length()) {\n                return true;\n            }\n            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {\n                return false;\n            }\n            \n            char temp = board[i][j];\n            board[i][j] = \'\\0\';\n            \n            if (backtrack(i + 1, j, k + 1) || backtrack(i - 1, j, k + 1) || \n                backtrack(i, j + 1, k + 1) || backtrack(i, j - 1, k + 1)) {\n                return true;\n            }\n            \n            board[i][j] = temp; \n            return false;\n        };\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (backtrack(i, j, 0)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n};\n\n```\n```java []\npublic class Solution {\n    public boolean exist(char[][] board, String word) {\n        int m = board.length;\n        int n = board[0].length;\n\n        boolean[][] visited = new boolean[m][n];\n        boolean result = false;\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (board[i][j] == word.charAt(0)) {\n                    result = backtrack(board, word, visited, i, j, 0);\n                    if (result) return true;\n                }\n            }\n        }\n        \n        return false;\n    }\n    \n    private boolean backtrack(char[][] board, String word, boolean[][] visited, int i, int j, int index) {\n        if (index == word.length()) {\n            return true;\n        }\n        \n        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) {\n            return false;\n        }\n        \n        visited[i][j] = true;\n        \n        if (backtrack(board, word, visited, i + 1, j, index + 1) ||\n            backtrack(board, word, visited, i - 1, j, index + 1) ||\n            backtrack(board, word, visited, i, j + 1, index + 1) ||\n            backtrack(board, word, visited, i, j - 1, index + 1)) {\n            return true;\n        }\n        \n        visited[i][j] = false;\n        return false;\n    }\n}\n\n```\n```javascript []\nvar exist = function(board, word) {\n    const m = board.length;\n    const n = board[0].length;\n    \n    const backtrack = (i, j, k) => {\n        if (k === word.length) {\n            return true;\n        }\n        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word.charAt(k)) {\n            return false;\n        }\n        \n        const temp = board[i][j];\n        board[i][j] = \'\\0\'; \n        \n        const result = backtrack(i + 1, j, k + 1) || \n                       backtrack(i - 1, j, k + 1) || \n                       backtrack(i, j + 1, k + 1) || \n                       backtrack(i, j - 1, k + 1);\n        \n        board[i][j] = temp; \n        return result;\n    };\n    \n    for (let i = 0; i < m; ++i) {\n        for (let j = 0; j < n; ++j) {\n            if (backtrack(i, j, 0)) {\n                return true;\n            }\n        }\n    }\n    return false;\n};\n\n```\n```C# []\npublic class Solution {\n    public bool Exist(char[][] board, string word) {\n        int m = board.Length;\n        int n = board[0].Length;\n        \n        Func<int, int, int, bool> backtrack = null;\n        backtrack = (i, j, k) => {\n            if (k == word.Length) {\n                return true;\n            }\n            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {\n                return false;\n            }\n            \n            char temp = board[i][j];\n            board[i][j] = \'\\0\';\n            bool result = backtrack(i + 1, j, k + 1) || \n                          backtrack(i - 1, j, k + 1) || \n                          backtrack(i, j + 1, k + 1) || \n                          backtrack(i, j - 1, k + 1);\n            \n            board[i][j] = temp; \n            return result;\n        };\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (backtrack(i, j, 0)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n\n```\n---\n\n\n![Screenshot 2023-08-20 065922.png](https://assets.leetcode.com/users/images/aff812e9-9751-4e8c-be5f-636ebb5e4fa4_1712103254.8384917.png)\n\n\n\n
['Array', 'String', 'Backtracking', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']