Python | Faster than 98% w/ Proof | Easy to Understand
\ndef exist(self, board: List[List[str]], word: str) -> bool:\n\t# Count number of letters in board and store it in a dictionary\n\tboardDic = defaultdict(int)\
```\ndef exist(self, board: List[List[str]], word: str) -> bool:\n\t# Count number of letters in board and store it in a dictionary\n\tboardDic = defaultdict(int)\n\tfor i in range(len(board)):\n\t\tfor j in range(len(board[0])):\n\t\t\tboardDic[board[i][j]] += 1\n\n\t# Count number of letters in word\n\t# Check if board has all the letters in the word and they are atleast same count from word\n\twordDic = Counter(word)\n\tfor c in wordDic:\n\t\tif c not in boardDic or boardDic[c] < wordDic[c]:\n\t\t\treturn False\n\n\t# Traverse through board and if word[0] == board[i][j], call the DFS function\n\tfor i in range(len(board)):\n\t\tfor j in range(len(board[0])):\n\t\t\tif board[i][j] == word[0]:\n\t\t\t\tif self.dfs(i, j, 0, board, word):\n\t\t\t\t\treturn True\n\n\treturn False\n\ndef dfs(self, i, j, k, board, word):\n\t# Recursion will return False if (i,j) is out of bounds or board[i][j] != word[k] which is current letter we need\n\tif i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or \\\n\t   k >= len(word) or word[k] != board[i][j]:\n\t\treturn False\n\n\t# If this statement is true then it means we have reach the last letter in the word so we can return True\n\tif k == len(word) - 1:\n\t\treturn True\n\n\tdirections = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n\n\tfor x, y in directions:\n\t\t# Since we can\'t use the same letter twice, I\'m changing current board[i][j] to -1 before traversing further\n\t\ttmp = board[i][j]\n\t\tboard[i][j] = -1\n\n\t\t# If dfs returns True then return True so there will be no further dfs\n\t\tif self.dfs(i + x, j + y, k + 1, board, word): \n\t\t\treturn True\n\n\t\tboard[i][j] = tmp\n```\n\n![image](https://assets.leetcode.com/users/images/fcebbf15-40ea-4bc2-9996-0eba8ddefef9_1660751925.768921.png)\n\n![image](https://assets.leetcode.com/users/images/62f7fc9e-8c35-4a80-b991-24266d5cbad2_1660753544.8842063.png)\n\n\n\n\n
['Backtracking', 'Recursion', 'Python', 'Python3']