【Video】Check 4 directions with counting length of a path.
Intuition\nCheck 4 directions with counting length of a path.\n\n# Solution Video\n\nhttps://youtu.be/8s8YjodDuTs\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget 
# Intuition\nCheck 4 directions with counting length of a path.\n\n# Solution Video\n\nhttps://youtu.be/8s8YjodDuTs\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 8,480\nThank you for your support!\n\n---\n\n# Approach\nSimply check 4 directions from every place and if we find the next target character, then move to that place.\n\nBut problem is that we don\'t know current length of path(= word), so every time we move to a new place, count `1` as a length of path, so that when the path length is equal to input word, we can return `True`.\n\n---\n\n# Discussion points\n\nimagine this metrics and a word.\n\n```\n["A","A","A","A"]\n["A","A","A","B"]\n["A","A","B","A"]\n\nword = "AAAAAAAABB"\n```\nIf we check the word from beginning(= `A`), we have to move a lot of places. But if we start from end(= `B`), we can immediately return `False` in many places.\n\nThis is depends on input word, but **we might reverse the input word if number of the first character is greater than number of the last character.**\n\nI implemented that logic. I think it\'s a good point to discuss with interviewers in real interview.\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n# Complexity\n- Time complexity: $$O(m * n * 4^len(word))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(4^len(word))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n```python []\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n    \n        rows, cols = len(board), len(board[0])\n        visited = set()\n\n        def dfs(r, c, k):\n            if k == len(word):\n                return True\n\n            if not (0 <= r < rows) or not (0 <= c < cols) or (r,c) in visited or board[r][c] != word[k]:\n                return False\n            \n            visited.add((r,c))\n            res = dfs(r+1, c, k+1) or dfs(r-1, c, k+1) or dfs(r, c+1, k+1) or dfs(r, c-1, k+1)\n            visited.remove((r,c))\n            return res\n             \n        count = {}\n        for c in word:\n            count[c] = 1 + count.get(c, 0)\n        \n        if count[word[0]] > count[word[-1]]:\n            word = word[::-1]\n        \n        for r in range(rows):\n            for c in range(cols):\n                if dfs(r, c, 0): return True\n        \n        return False\n```\n```javascript []\nvar exist = function(board, word) {\n    const rows = board.length;\n    const cols = board[0].length;\n    const visited = new Set();\n\n    const dfs = (r, c, k) => {\n        if (k === word.length) return true;\n        if (r < 0 || r >= rows || c < 0 || c >= cols || visited.has(`${r},${c}`) || board[r][c] !== word[k]) {\n            return false;\n        }\n\n        visited.add(`${r},${c}`);\n        const res = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);\n        visited.delete(`${r},${c}`);\n        return res;\n    };\n\n    const count = {};\n    for (const c of word) {\n        count[c] = (count[c] || 0) + 1;\n    }\n\n    if (count[word[0]] > count[word[word.length - 1]]) {\n        word = word.split(\'\').reverse().join(\'\');\n    }\n\n    for (let r = 0; r < rows; r++) {\n        for (let c = 0; c < cols; c++) {\n            if (dfs(r, c, 0)) return true;\n        }\n    }\n\n    return false;    \n};\n```\n```java []\nclass Solution {\n    private int rows;\n    private int cols;\n    private Set<String> visited;\n\n    public boolean exist(char[][] board, String word) {\n        rows = board.length;\n        cols = board[0].length;\n        visited = new HashSet<>();\n\n        Map<Character, Integer> count = new HashMap<>();\n        for (char c : word.toCharArray()) {\n            count.put(c, count.getOrDefault(c, 0) + 1);\n        }\n\n        if (count.getOrDefault(word.charAt(0), 0) > count.getOrDefault(word.charAt(word.length() - 1), 0)) {\n            word = new StringBuilder(word).reverse().toString();\n        }\n\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (dfs(board, word, r, c, 0)) {\n                    return true;\n                }\n            }\n        }\n\n        return false;\n    }\n\n    private boolean dfs(char[][] board, String word, int r, int c, int k) {\n        if (k == word.length()) {\n            return true;\n        }\n\n        if (r < 0 || r >= rows || c < 0 || c >= cols || visited.contains(r + "," + c) || board[r][c] != word.charAt(k)) {\n            return false;\n        }\n\n        visited.add(r + "," + c);\n        boolean res = dfs(board, word, r + 1, c, k + 1) ||\n                      dfs(board, word, r - 1, c, k + 1) ||\n                      dfs(board, word, r, c + 1, k + 1) ||\n                      dfs(board, word, r, c - 1, k + 1);\n        visited.remove(r + "," + c);\n        return res;\n    }    \n}\n```\n```C++ []\nclass Solution {\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        int rows = board.size();\n        int cols = board[0].size();\n        unordered_set<string> visited;\n\n        auto dfs = [&](int r, int c, int k, auto& dfs) -> bool {\n            if (k == word.length()) {\n                return true;\n            }\n\n            if (r < 0 || r >= rows || c < 0 || c >= cols || visited.count(to_string(r) + "," + to_string(c)) || board[r][c] != word[k]) {\n                return false;\n            }\n\n            visited.insert(to_string(r) + "," + to_string(c));\n            bool res = dfs(r + 1, c, k + 1, dfs) || dfs(r - 1, c, k + 1, dfs) || dfs(r, c + 1, k + 1, dfs) || dfs(r, c - 1, k + 1, dfs);\n            visited.erase(to_string(r) + "," + to_string(c));\n            return res;\n        };\n\n        unordered_map<char, int> count;\n        for (char c : word) {\n            count[c]++;\n        }\n\n        if (count[word[0]] > count[word.back()]) {\n            reverse(word.begin(), word.end());\n        }\n\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (dfs(r, c, 0, dfs)) {\n                    return true;\n                }\n            }\n        }\n\n        return false;        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n### 1. Initialize Board Dimensions and Visited Set\n\n**Main Logic:**\nGet the dimensions of the board and initialize a set to track visited cells.\n\n**Code:**\n```python\nrows, cols = len(board), len(board[0])\nvisited = set()\n```\n\n**Explanation:**\n- `rows` and `cols` obtain the number of rows and columns of the board, respectively.\n- `visited` is a set used to keep track of cells that have been visited to prevent revisiting the same cell.\n\n---\n\n### 2. Define the DFS (Depth-First Search) Function\n\n**Main Logic:**\nDefine an internal function `dfs` to perform a depth-first search starting from a cell (r, c) to find the k-th character of the word.\n\n**Code:**\n```python\ndef dfs(r, c, k):\n    if k == len(word):\n        return True\n\n    if not (0 <= r < rows) or not (0 <= c < cols) or (r,c) in visited or board[r][c] != word[k]:\n        return False\n\n    visited.add((r,c))\n    res = dfs(r+1, c, k+1) or dfs(r-1, c, k+1) or dfs(r, c+1, k+1) or dfs(r, c-1, k+1)\n    visited.remove((r,c))\n    return res\n```\n\n**Explanation:**\n- If `k` equals the length of the word, it means all characters have been matched, so return `True`.\n- If the current cell is out of bounds, already visited, or the character does not match the current character in the word, return `False`.\n- Add the current cell to the `visited` set and recursively call `dfs` in all four directions (up, down, left, right).\n- After exploring, remove the current cell from the `visited` set and return the result.\n\n---\n\n### 3. Count Character Frequencies in the Word\n\n**Main Logic:**\nCount the occurrences of each character in the word and store it in a dictionary.\n\n**Code:**\n```python\ncount = {}\nfor c in word:\n    count[c] = 1 + count.get(c, 0)\n```\n\n**Explanation:**\n- `count` is a dictionary that records the frequency of each character in the word.\n- Iterate through each character in the word and update its count in the dictionary. If the character is not already in the dictionary, start with a count of `0`.\n\n---\n\n### 4. Reverse the Word Based on Character Frequency\n\n**Main Logic:**\nIf the frequency of the first character in the word is greater than the frequency of the last character, reverse the word.\n\n**Code:**\n```python\nif count[word[0]] > count[word[-1]]:\n    word = word[::-1]\n```\n\n**Explanation:**\n- Reverse the word if the frequency of the first character is greater than the frequency of the last character. This reversal can help improve the efficiency of the search in some cases.\n\n---\n\n### 5. Start DFS from Each Cell in the Board\n\n**Main Logic:**\nPerform DFS from each cell in the board to check if the word can be found.\n\n**Code:**\n```python\nfor r in range(rows):\n    for c in range(cols):\n        if dfs(r, c, 0): return True\n```\n\n**Explanation:**\n- Loop through each cell in the board and start DFS from that cell.\n- If `dfs` returns `True` for any cell, it means the word is found in the board, so return `True`. If no cell results in finding the word, continue to the next cell.\n\n---\n\n### 6. Return `False` if the Word is Not Found\n\n**Main Logic:**\nIf the word is not found in any of the cells, return `False`.\n\n**Code:**\n```python\nreturn False\n```\n\n**Explanation:**\n- If the word is not found in any cell after checking all cells, return `False`, indicating that the word does not exist on the board.\n\n---\n\nThank you for reading my post. Please upvote it and don\'t forget to subscribe to my channel!\n\n### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### \u2B50\uFE0F Related Video\n\n#200 - Number of Islands\n\nhttps://youtu.be/HpinqiqiXUQ\n\n\n
['C++', 'Java', 'Python3', 'JavaScript']