Python 3   ||   dfs with a little bit of pruning  ||   T/S: 99% / 99%
\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n\n        row, col = len(board), len(board[0])\n        R, C, seen = range(r
```\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n\n        row, col = len(board), len(board[0])\n        R, C, seen = range(row), range(col), set()\n\n        def dfs(coord, i=0):\n            \n            if len(word) == i: return True\n            \n            r,c = coord\n\n            if (r not in R or c not in C or \n                coord in seen            or \n                board[r][c] != word[i]): return False\n            \n            seen.add(coord)\n\n            res = (dfs((r+1,c), i+1) or dfs((r,c+1), i+1) or\n                   dfs((r-1,c), i+1) or dfs((r,c-1), i+1))\n            \n            seen.remove(coord)\n\n            return res\n\n        boardCt, wrdCt = Counter(chain(*board)), Counter(word)\n        if any (boardCt[ch] < wrdCt[ch] for ch in wrdCt): return False\n\n        if boardCt[word[0]] > boardCt[word[-1]]: word = word[::-1]\n        \n        return any(dfs((r, c))  for c in C for r in R)\n```\n[https://leetcode.com/problems/word-search/submissions/848874764/](https://leetcode.com/problems/word-search/submissions/848874764/)\n\nI could be wrong, but I think that time complexity is *O*(*MN* * 4^*L*) and space complexity is *O*(*L*), in which *M*, *N* ~ `row`, `col` and *L* ~ `len(word)`.
['Python', 'Python3']