My accepted Python solution, easy to understand.Also a problem about python "map"


  • 0
    R
    class Solution(object):
    def __init__(self):
        self.le=0
        self.lee=0
        self.alen=0
        self.map={}
    def judge(self,i,j,board,index,word):
        if i>=self.le or j>=self.lee or i<0 or j<0 or board[i][j]!=word[index]:
            return False
    ##elif (i,j) in self.map:
        ##if self.map[(i,j)]:
             ##return False
        elif index==self.alen-1:
            return True
        else:
            temp=board[i][j]
            board[i][j]="#"
            ##self.map[(i,j)]=True
            if self.judge(i,j+1,board,index+1,word):
                return True
            if self.judge(i-1,j,board,index+1,word):
                return True
            if self.judge(i,j-1,board,index+1,word):
                return True
            if self.judge(i+1,j,board,index+1,word):
                return True
            ##self.map[(i,j)]=False
            board[i][j]=temp
            return False
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.le=len(board)
        start=[]
        if self.le==0:
            return False
        else:
            self.lee=len(board[0])
        for i in range(self.le):
            for j in range(self.lee):
                if board[i][j]==word[0]:
                    start.append([i,j])
        if len(start)==0:
            return False
        else:
            self.alen=len(word)
            for i in range(len(start)):
                ans=self.judge(start[i][0],start[i][1],board,0,word)
                self.map.clear()
                if ans:
                    return ans
            return False
    

    In the code, I just found the start symbol first, and then do some judgements first, but it turns out you don't need to do that, just use the "judge" function and then start from the first letter to the last, it is ok, but using that way(find the start symbol) makes more sense to me.
    And i found a problem, when i try to use map to judge whether this position is visited or not, i cannot figure it out, always existing bugs, and when i use a temp and "#" label to help me label a position as visited, it works! I don't know why. I comment out the method using map, i think it should work. I just confused, anyone help me?


Log in to reply
 

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