Nevermind. I figured out my issue.


  • 0
    E

    My solution,

    class Solution(object):
        def existsAt(self, board, row, col, i, word, visited={}):
            if board[row][col] != word[i]:
                return False
            if i >= len(word)-1:
                return True
        
            visited[(row,col)] = 1
            
            res = False
            for dx, dy in ((0,1),(0,-1),(1,0),(-1,0)):
                if row+dy < 0 or row+dy >= len(board) or col+dx < 0 or col+dx >= len(board[0]):
                    continue
                if (row+dy,col+dx) in visited:
                    continue
                res = res or self.existsAt(board, row+dy, col+dx, i+1, word, visited)
            return res
        
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            for row in xrange(len(board)):
                for col in xrange(len(board[0])):
                    if board[row][col] == word[0]:
                        if self.existsAt(board, row, col, 0, word):
                            return True
            return False
    

    fails on Submit Solution for ["aa"] "aa", but works fine when I run that test case manually.

    Is there a bug in the solution processor or did I miss something here?


  • 0
    E

    NO, not a bug in the solution processor.

    The issue was with the visited dict I was passing around, which I treated as pass-by-value but is pass-by-reference.

    I'm still not quite sure why Custom Testcase worked but Submit did not, but I think it's because the state of visited was being carried between test cases.

    This new solution works (note: still slow, only faster than 20% of Python solutions):

    class Solution(object):
        def existsAt(self, board, row, col, i, word, visited=[]):
            if board[row][col] != word[i]:
                return False
            if i >= len(word)-1:
                return True
                
            res = False
            for dx, dy in ((0,1),(0,-1),(1,0),(-1,0)):
                if row+dy < 0 or row+dy >= len(board) or col+dx < 0 or col+dx >= len(board[0]):
                    continue
                if (row+dy, col+dx) in visited:
                    continue
                res = res or self.existsAt(board, row+dy, col+dx, i+1, word, visited+[(row,col)])
            return res
                
        def exist(self, board, word):
            """ 
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            for row in xrange(len(board)):
                for col in xrange(len(board[0])):
                    if board[row][col] == word[0]:
                        if self.existsAt(board, row, col, 0, word, []):
                            return True
            return False
    

Log in to reply
 

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