Time Limit Exceed on my python solution


  • 2
    S

    Hi there, I am trying to use Python to solve the problem. I use the DFS method but got a TLE. I have seen other solutions using C++ or Java. But I think the basic idea of those Accepted codes are just the same with mine. So any suggestions on my code? I will very appreciate your suggestions!

    class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        for i in range(0, len(board)):
            s = board[i]
            for j in range(0, len(s)):
                if board[i][j] == word[0]:
                    visited = [[False for m in range(len(board[0]))] for n in range(len(board))]
                    if DFS(board, word, visited, 0, i, j):
                        return True
        return False
    def DFS(board, word, visited, index, i, j):
    if i >= 0 and j >=0 and i < len(board) and j < len(board[0]) \
         and board[i][j] == word[index] and visited[i][j] == False:
        visited[i][j] = True
        if index + 1 == len(word):
            return True
        if DFS(board, word, visited, index + 1, i + 1, j):
            return True
        elif DFS(board, word, visited, index + 1, i - 1, j):
            return True
        elif DFS(board, word, visited, index + 1, i , j + 1):
            return True
        elif DFS(board, word, visited, index + 1, i , j - 1):
            return True
    return False

  • 3
    R

    In fact I think your code is much conciser than my java version (Maybe it is just due to the different languages). So I corrected all your errors.

    class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
        def exist(self, board, word):
            visited = [[False for m in range(len(board[0]))] for n in range(len(board))] #Key improvement
            for i in range(0,len(board)):
                for j in range(0,len(board[0])):
                    if board[i][j] == word[0]:
                        if self.DFS(board, word, visited, 0, i, j):
                            return True
            return False
        
        def DFS(self,board, word, visited, index, i, j):# Why do you have no self in your code? 
            if i >= 0 and j >=0 and i < len(board) and j < len(board[0]) \
         and board[i][j] == word[index] and visited[i][j] == False:
                visited[i][j] = True
                if index + 1 == len(word):
                    return True
                if self.DFS(board, word, visited, index + 1, i + 1, j):
                    return True
                if self.DFS(board, word, visited, index + 1, i - 1, j):
                    return True
                if self.DFS(board, word, visited, index + 1, i , j + 1):
                    return True
                if self.DFS(board, word, visited, index + 1, i , j - 1):
                    return True
                visited[i][j]=False #Key improvement
            return False

  • 0
    S

    Hi reeclapple, thank you very much for your answer. I think I find the reason why I got a TLE on my previous code. in my exist function I had to initialise the visited array every time before the search. But in your way, it's faster without initialising the visited very often.


  • 0
    R

    Also you have to unlabel a point if all of its four direction return false;


Log in to reply
 

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