✅ [Python/C++] faster than 99% DFS (explained)
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs a Depth First Search* approach (with optimization) to find a word on the board.  Time
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs a *Depth First Search* approach (with optimization) to find a word on the board.  Time complexity is **O(M\\*N\\*4^L)**. Space complexity is **O(M\\*N)**.\n****\n\n**Comment.** A straightforward DFS won\'t work here well (possible TLEs) due to significant amount of branches. The best strategy is to optimize (reduce) the number of branches at early stages, namely, starting from the first letter. The underlying symmetry of the problem, actually, allows us to do that, i.e., to reverse a word if it\'s more appropriate (less branches) to start searching from the end.\n\n**Python.** This [**solution**](https://leetcode.com/submissions/detail/848875896/) demonstrated **36 ms (99.76%) runtime**.\n```\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        \n        m, n = len(board), len(board[0])\n        \n        if len(word) > m * n: return False                            # [a] trivial case to discard\n\n        if not (cnt := Counter(word)) <= Counter(chain(*board)):      # [b] there are not enough\n            return False                                              #     letters on the board\n        \n        if cnt[word[0]] > cnt[word[-1]]:                              # [c] inverse word if it\'s better\n             word = word[::-1]                                        #     to start from the end\n        \n        def dfs(i, j, s):                                             # recursive postfix search\n            \n            if s == len(word) : return True                           # [1] found the word\n            \n            if 0 <= i < m and 0 <= j < n and board[i][j] == word[s]:  # [2] found a letter\n                board[i][j] = "#"                                     # [3] mark as visited\n                adj = [(i,j+1),(i,j-1),(i+1,j),(i-1,j)]               # [4] iterate over adjacent cells...\n                dp = any(dfs(ii,jj,s+1) for ii,jj in adj)             # [5] ...and try next letter\n                board[i][j] = word[s]                                 # [6] remove mark\n                return dp                                             # [7] return search result\n\n            return False                                              # [8] this DFS branch failed\n                \n        return any(dfs(i,j,0) for i,j in product(range(m),range(n)))  # search starting from each position\n```\n\n**C++.**\n```\nclass Solution \n{\npublic:\n    bool exist(vector<vector<char>>& board, string word) \n    {\n        int dirs[5] = {0, -1, 0, 1, 0};\n        map<char,int> cnt;\n        int m = board.size(), n = board[0].size(), l = word.size();\n        \n        for (char c : word) cnt[c] += 1;\n        \n        if (cnt[word[0]] > cnt[word[l-1]])\n            reverse(word.begin(), word.end());\n        \n        function<bool(int,int,int)> dfs;\n        dfs = [&] (int i, int j, int s) -> bool\n        {\n            if (s == l) return true;\n            \n            if (i < 0 or i >= m or j < 0 or j >= n) return false;\n            if (board[i][j] != word[s])             return false;\n            \n            board[i][j] = \'#\';\n            for (int d = 0; d < 4; ++d)\n                if (dfs(i + dirs[d], j + dirs[d+1], s+1)) return true;\n            board[i][j] = word[s];\n            \n            return false;\n        };\n        \n        for (int i = 0; i < m; ++i)\n            for (int j = 0; j < n; ++j)\n                if (dfs(i, j, 0)) return true;\n        \n        return false;\n    }\n};\n```
[]