LeetCode 79. Word Search problems storing previously visited

user_8358537 0
Viewed 196

My question is very similar to: leetcode 79 word search python solution, need help on debugging

The case that I'm having trouble with is the same:

[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"

The problem I'm having is basically the same. The aforementioned question is answered, so I understand the principle idea of the problem (if I delete the part about checking previously visited, the code succeeds for this case), but can somebody explain step by step why my visited list is getting polluted?

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        top = -1
        bottom = len(board)
        rowstart = -1
        rowend = len(board[0])
        def traverse(a, b, index, visited):
            print(a,b)
            print(visited)
            print()
            if index == len(word):
                return True
            if a == top or a == bottom or b == rowstart or b == rowend:
                return False
            if board[a][b] != word[index]:
                return False
            if [a,b] in visited:
                return False
            visited.append([a,b])
            return (
                traverse(a+1, b, index+1, visited)
                or
                traverse(a, b+1, index+1, visited)
                or
                traverse(a-1, b, index+1, visited)
                or
                traverse(a, b-1, index+1, visited)
            )
        for c in range(0, len(board)):
            for d in range(0, len(board[0])):
                if board[c][d] == word[0]:
                    if traverse(c,d,0,[]) == True:
                        return True
        return False
recursion algorithm python
1 Answers

My understanding of your code is that you're doing a DFS to find a sequence of tiles that form the word. If this is true, then you need to backtrack whenever you reach a state where it's impossible to form the word by recursing upwards and removing that tile from visited (remember that this list is shared across all recursive calls to traverse()).

Here is a solution that will pass the test case you've given.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        top = -1
        bottom = len(board)
        rowstart = -1
        rowend = len(board[0])
        def traverse(a, b, index, visited):
            if index == len(word):
                return True
            if a == top or a == bottom or b == rowstart or b == rowend:
                return False
            if board[a][b] != word[index]:
                return False
            if [a,b] in visited:
                return False
            visited.append([a,b])
            if (
                traverse(a+1, b, index+1, visited)
                or
                traverse(a, b+1, index+1, visited)
                or
                traverse(a-1, b, index+1, visited)
                or
                traverse(a, b-1, index+1, visited)
            ):
                return True
            else:
                visited.pop()
                return False
        for c in range(0, len(board)):
            for d in range(0, len(board[0])):
                if board[c][d] == word[0]:
                    if traverse(c,d,0,[]) == True:
                        return True
        return False

This code, however, will TLE. The simplest way to get under the time limit is to notice that whenever we backtrack, we don't need to store the order of the tiles we visit; we just have to know which tile to remove from our visited set. This means that we can use a set of tuples rather than a list of lists, which makes lookup in visited faster.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        top = -1
        bottom = len(board)
        rowstart = -1
        rowend = len(board[0])
        def traverse(a, b, index, visited):
            if index == len(word):
                return True
            if a == top or a == bottom or b == rowstart or b == rowend:
                return False
            if board[a][b] != word[index]:
                return False
            if (a, b) in visited:
                return False
            visited.add((a,b))
            if (
                traverse(a+1, b, index+1, visited)
                or
                traverse(a, b+1, index+1, visited)
                or
                traverse(a-1, b, index+1, visited)
                or
                traverse(a, b-1, index+1, visited)
            ):
                return True
            else:
                visited.remove((a, b))
                return False
        for c in range(0, len(board)):
            for d in range(0, len(board[0])):
                if board[c][d] == word[0]:
                    if traverse(c,d,0,set()) == True:
                        return True
        return False

This will pass LeetCode's execution time limits.

user_177698150
Related