Word search - Python3 Solution with a Detailed Explanation
This solution comes from here. The idea is that you loop over every element of a matrix one by one (lines #1 and #2), and check whether you can find the word. T
This solution comes from [here](https://leetcode.com/problems/word-search/discuss/27665/Python-simple-dfs-solution). The idea is that you loop over every element of a matrix one by one (lines `#1` and `#2`), and check whether you can find the word. The main part is the `dfs` function that for each value (`board[i][j]`) check whether it\'s the first letter of the `word`. If it\'s not it returns `False` (line `#5`). Otherwise, it moves forward (line `#4`). After satisfying line `#4` (meaning first letter is found), we replace  that cell in `board` with space so that we now we\'ve visited it (line `#6`). Then, we try four different scenarios in the neighborhood of `[i][j]` and see whether we can find the second letter of `word` (line `#7, 8, 9, 10`). This is done recursively. After we find the first letter in line `#4`, we focus on the rest of the `word`, meaning `word[1:]`. If the second letter is one of the right, left, top, or bottom cells of `board[i][j]`, we focus of `word[2:]` in the next cycle. We keep doing this until we find all the letters. Now say, we find the first letter, but the second letter is not in the neighborhood, we go to a new `board[i][j]` by checking a new cell in lines `#1, 2, 3` and start the process from scratch for the whole `word`. \n\n\nNote that the conditions of lines `#7` ( `i>0`), `#8` (` i < len(board) - 1 `), etc. takes care of matrix edges. If it wasn\'t there, and you\'re on the first column of matrix (`j=0`), then `j - 1` would give you `-1` which is corresponding to the right side. \n\n\n\n\nDoes this make sense? \n\n\n```\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        if not board:\n            return False\n        if not word:\n            return True\n        \n        for i in range(len(board)): # 1\n            for j in range(len(board[0])): # 2\n                if self.dfs(board, word, i, j): #3\n                    return True\n        return False   \n        \n    \n    def dfs(self, board, word, i, j):\n        if board[i][j] == word[0]: #4\n            if not word[1:]:\n                return True\n        \n            board[i][j] = " " #6\n        \n            if i > 0 and self.dfs(board, word[1:], i - 1, j): #7\n                return True\n            if i < len(board) - 1 and self.dfs(board, word[1:], i + 1, j): #8\n                return True\n            if j > 0 and self.dfs(board, word[1:], i, j - 1): #9\n                return True\n            if j < len(board[0]) - 1 and self.dfs(board, word[1:], i, j + 1): #10\n                return True\n        \n            board[i][j] = word[0]\n            return False\n        else: #5\n            return False\n```\n\n========================================================================\nFinal note: Please let me know if you found any typo/error/etc. I\'ll try to fix it. \n\nFinal note 2: Explaning things in a simple language is instructive for me. Thanks for reading.
['Python', 'Python3']