Not all the combinations are tried, but I still got a LTE error.


  • 0
    L
    class Solution:
        # @param board, a list of lists of 1 length string
        # @param word, a string
        # @return a boolean
        def exist(self, board, word):
            row = len(board)
            col = len(board[0])
            path = {}
            flag = False
            for i in xrange(row):
                for j in xrange(col):
                    if board[i][j] == word[0]:
                        location = (i,j)
                        path[location] = True
                        flag = self.get_path(location, word, 0+1, path, board)
                        if flag:
                            return flag
                        else:
                            path[location] = False
            return flag
            
        def get_path(self, location, word, position, path, board):
            if position == len(word):
                return True
            neighbours = []
            if location[0] >= 1:
                neighbours.append((location[0]-1, location[1]))
            elif location[0] <= len(board)-2:
                neighbours.append((location[0]+1, location[1]))
                
            if location[1] >= 1 :
                neighbours.append((location[0], location[1]-1))
            elif location[1] <= len(board[0])-2:
                neighbours.append((location[0], location[1]+1))
                
            flag = False
            for neighbour in neighbours:
                if board[neighbour[0]][neighbour[1]] == word[position]:
                    if path.get(neighbour, False):
                        continue
                    path[neighbour] = True
                    flag = self.get_path(neighbour, word, position+1, path, board)
                    if flag:
                        break
                    else:
                        path[neighbour] = False
            return flag

Log in to reply
 

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