Why Python BFS get Time Exceed Error?


  • 0
    A

    I use a typical BFS solution, but get a TLE error. It looks the python time limit is set too tight?
    Any comments to the reason?

    from Queue import deque
    class Solution(object):
        def numIslands(self, G):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            M = len(G)
            if M == 0: return 0
            N = len(G[0])
            if N == 0: return 0
            count = 0
            for i in range(M):
                for j in range(N):
                    if G[i][j] == '1':
                        count += 1
                        self.flood(G, i, j)
            return count
    
        def flood(self, G, r, c):
            M, N = len(G), len(G[0])
            Q = deque()
            Q.append((r, c))
            while len(Q):
                top = Q.popleft()
                i, j = top[0], top[1]
                G[i][j] = ' '
                if i - 1 >= 0 and G[i - 1][j] == '1':
                    Q.append((i - 1, j))
                if i + 1 < M and G[i + 1][j] == '1':
                    Q.append((i + 1, j))
                if j - 1 >= 0 and G[i][j - 1] == '1':
                    Q.append((i, j - 1))
                if j + 1 < N and G[i][j + 1] == '1':
                    Q.append((i, j + 1))
    

  • 0
    S

    you need to set G[i][j] = ' ' when you add it to the deque, otherwise you will add duplicate points and greatly increase the repeated cases.


Log in to reply
 

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