Why is my python solution not working? Logically it seems correct..


  • 0
    I
    class Solution(object):
    def findWord(self, word, board, wordIdx, row, col, visited):
        rows = len(board)
        cols = len(board[0])
        
        if (row < 0) or (row >= rows) or (col < 0) or (col >= cols) or visited[row][col] or word[wordIdx] != board[row][col]:
            return False
        
        if word[wordIdx] == board[row][col]:
            if wordIdx == len(word) - 1:
                return True
            
            visited[row][col] = True
    
            #up
            if self.findWord(word, board, wordIdx + 1, row - 1, col, visited):
                return True
                
            #down
            if self.findWord(word, board, wordIdx + 1, row + 1, col, visited):
                return True 
                
            #left
            if self.findWord(word, board, wordIdx + 1, row, col - 1, visited):
                return True
                
            #right
            if self.findWord(word, board, wordIdx + 1, row, col + 1, visited):
                return True
    
        return False
    
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not word or len(word) == 0:
            return False
        
        rows = len(board)
        cols = len(board[0])
        
        for row in xrange(rows):
            for col in xrange(cols):
                if board[row][col] == word[0]:
                    visited = [[False]*cols]*rows
                    
                    if self.findWord(word, board, 0, row, col, visited):
                        return True
                        
        return False

  • 0
    B

    something in common with my version

    class Solution(object):
    def find(self,board,path,i,j,word):

        if word=='':
            return True
        if i<0 or i>len(board)-1 or j <0 or j>len(board[0])-1 or board[i][j] != word[0]:
            return False
        if (i,j) in path:
            return False
    
        if self.find(board,path+[(i,j)],i+1,j,word[1:]):return True
        if self.find(board,path+[(i,j)],i-1,j,word[1:]):return True
        if self.find(board,path+[(i,j)],i,j+1,word[1:]):return True
        if self.find(board,path+[(i,j)],i,j-1,word[1:]):return True
        return False
    
    
    def first_letter(self,board,word,temp):
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if word[0] == board[i][j]:
                    temp.append((i,j))
    
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        temp=[]
        self.first_letter(board,word,temp)
        for i in temp:
            if self.find(board,[],i[0],i[1],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.