A non-recursive solution, but slow


  • 0
    W
    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[0])
        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[0]:
                    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[0]
                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 ord and 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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.