[Python] dfs backtracking solution, explained
In general I think this problem do not have polynomial solution, so we need to check a lot of possible options. What should we use in this case: it is bruteforc
In general I think this problem do not have polynomial solution, so we need to check a lot of possible options. What should we use in this case: it is bruteforce, with backtracking. Let `dfs(ind, i, j)` be our backtracking function, where `i` and `j` are coordinates of cell we are currently in and `ind` is index of letter in `word` we currently in. Then our `dfs` algorithm will look like:\n1. First, we have `self.Found` variable, which helps us to finish earlier if we already found solution.\n2. Now, we check if `ind` is equal to `k` - number of symbols in `word`. If we reach this point, it means we found `word`, so we put `self.Found` to `True` and return back.\n3. If we go outside our board, we return back.\n4. If symbol we are currently on in `words` is not equal to symbol in table, we also return back.\n5. Then we visit all neibours, putting `board[i][j] = "#"` before - we say in this way, that this cell was visited and changing it back after.\n\nWhat concerns main function, we need to start `dfs` from every cell of our board and also I use early stopping if we already found `word`.\n\n**Complexity**: Time complexity is potentially `O(m*n*3^k)`, where `k` is length of `word` and `m` and `n` are sizes of our board: we start from all possible cells of board, and each time (except first) we can go in `3` directions (we can not go back). In practice however this number will be usually much smaller, because we have a lot of dead-ends. Space complexity is `O(k)` - potential size of our recursion stack. If you think this analysis can be improved, please let me know!\n\n```\nclass Solution:\n    def exist(self, board, word):\n        def dfs(ind, i, j):\n            if self.Found: return        #early stop if word is found\n\n            if ind == k:\n                self.Found = True                #for early stopping\n                return \n\n            if i < 0 or i >= m or j < 0 or j >= n: return \n            tmp = board[i][j]\n            if tmp != word[ind]: return\n\n            board[i][j] = "#"\n            for x, y in [[0,-1], [0,1], [1,0], [-1,0]]:\n                dfs(ind + 1, i+x, j+y)\n            board[i][j] = tmp\n        \n        self.Found = False\n        m, n, k = len(board), len(board[0]), len(word)\n        \n        for i, j in product(range(m), range(n)):\n            if self.Found: return True          #early stop if word is found\n            dfs(0, i, j)\n        return self.Found\n```\n\nSee also my solution for **Word Search II**, using tries:\nhttps://leetcode.com/problems/word-search-ii/discuss/712733/Python-Trie-solution-with-dfs-explained\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Backtracking']