class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ if word == "": return True s, use = ,  Y, X = len(board), len(board) if len(word) > Y * X: return False for y in range(Y): use.append([False] * X) for y in range(Y): for x in range(X): if board[y][x] == word: s.append(((y, x), 0)) s.append(((y, x), word[1:])) while s: (y, x), word = s.pop() if word == "": return True if word == 0: use[y][x] = False else: use[y][x] = True head = word for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)): if 0 <= nx < X and 0 <= ny < Y and board[ny][nx] == head and not use[ny][nx]: s.append(((ny, nx), 0)) s.append(((ny, nx), word[1:])) return False
Notice that when I push items into the stack, I pushed it twice, so when the first one gets popped, I start to visit its children; when the second one gets popped, I know that all its children have been dealt with.
use matrix is not necessary as we can modify the board in-place. The way I did it was with
chr functions to convert betwwen char and its numeric representation. One can also wrap the char in a tuple or something to mark the difference here.
This solution is not fast, but it's space efficient due to the elimation of recursive calls.