Python DFS TLE, Help!


  • 0
    G
    class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        X = len(board)
        Y = len(board[0])
        cor_add = lambda x, y: (x[0]+y[0], x[1]+y[1])
        neighbor = [(1,0), (-1,0), (0,1), (0,-1)]
        stack = []
        for i in xrange(X):
            for j in xrange(Y):
                if board[i][j] == word[0]:
                    stack.append(([(i, j)], word[1:]))
        while not stack == []:
            s = stack.pop()
            c, w = s
            if w == '':
                return True
            l = c[-1]
            ln = [cor_add(l, n) for n in neighbor]
            for x in ln:
                if not (x[0]>=0 and x[0]<X and x[1]>=0 and x[1]<Y):
                    continue
                if not (board[x[0]][x[1]] == w[0]):
                    continue
                if x not in c:
                    stack.append((c + [x], w[1:]))
        return False
    

    I ran test cases of:
    ==== 1, 2, 3

    examples given in the problem

    ==== 4

    ["aaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaab"]

    "baaaaaaaaaaaaaaaaaa...

    ==== 5

    ["elxllvxegzmvgnhrypvagxrgwktiqnyuavfnsfsbgewnrferubrcykjwveenrfhtamhvtzwafspzxvqtwkxwwgttkzgdenzhcgcvhyxosonrjgmhsjeo", ...
    "oajgdkcokvfpdaslnmomrpgwitwdoku"

    On my MBP:

    $ time python word-search.py

    True

    True

    False

    True

    True

         11514 function calls in 0.087 seconds
    

    Ordered by: standard name

    ncalls tottime percall cumtime percall filename:lineno(function)

        1    0.000    0.000    0.087    0.087 <string>:1(<module>)
        1    0.001    0.001    0.087    0.087 word-search.py:31(main)
        5    0.079    0.016    0.086    0.017 word-search.py:5(exist)
     6988    0.006    0.000    0.006    0.000 word-search.py:8(<lambda>)
       10    0.000    0.000    0.000    0.000 {len}
     2757    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     1751    0.000    0.000    0.000    0.000 {method 'pop' of 'list' objects}
    

    real 0m0.116s

    user 0m0.101s

    sys 0m0.013s

    I don't know how much the time limit is, but I think you need to give python at least 100ms per test case.


  • 0
    L

    Hi, there.
    It is very obvious that this problem should be done with some backtracking or recursion. Although your code is not using recursion explicitly, you are using stack to memorize the previous states.

    I think the most important message of this problem is to teach us how to break the recursive loop in some condition to avoid the unnecessary checking, so that we do not need to search the whole dfs tree.

    More specifically, we do not need to generate all the neighbors for each position meets the requirement here. If there are multiple characters in the board same with desired one and say, if we can find the word going through the first one, why do we bother to keep the rest in the stack and check them?

    Here is the code which explains the idea avoiding redundant searching and checking.

    class Solution:
        # @param {character[][]} board
        # @param {string} word
        # @return {boolean}
        def _exist(self, board, word, i, j):
            if board[i][j] == word[0]:
                if not word[1:]:
                    return True
                board[i][j] = " "
                if 0 < i and self._exist(board, word[1:], i-1, j):
                    return True
                if i < len(board)-1 and self._exist(board, word[1:], i+1, j):
                    return True
                if 0 < j and self._exist(board, word[1:], i, j-1):
                    return True
                if j < len(board[0])-1 and self._exist(board, word[1:], i, j+1):
                    return True
                board[i][j] = word[0]
                return False
            return False
    
        def exist(self, board, word):
            if len(word) > len(board) * len(board[0]):
                return False
            for i in range(len(board)):
                for j in range(len(board[0])):
                        if self._exist(board, word, i, j):
                            return True
            return False
    

    It takes 3ms for the following case, while your code takes around 100ms. With more testcases it will cause TLE. Hope this can help.

    board = ["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"]

    word =
    "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"


Log in to reply
 

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