Why I get TLE by using BFS and iteration?


  • 0
    A

    Why my code get TLE? I use BFS. Instead of recurrsion, I use iteration. It should be faster than DFS and recurrsion. Can anyone help?

    class Solution(object):
    	def find(self,board,l,word):
    		position=l[-1]
    		potential=[]
    		if position[0]>0:
    			if [position[0]-1,position[1]] not in l:
    				if board[position[0]-1][position[1]]==word[(len(l))]:
    					potential.append([position[0]-1,position[1]])
    		if position[0]<(len(board)-1):
    			if [position[0]+1,position[1]] not in l:
    				if board[position[0]+1][position[1]]==word[(len(l))]:
    					potential.append([position[0]+1,position[1]])
    		if position[1]>0:
    			if [position[0],position[1]-1] not in l:
    				if board[position[0]][position[1]-1]==word[(len(l))]:
    					potential.append([position[0],position[1]-1])
    		if position[1]<(len(board[0])-1):
    			if [position[0],position[1]+1] not in l:
    				if board[position[0]][position[1]+1]==word[(len(l))]:
    					potential.append([position[0],position[1]+1])
    		return potential
    
    	def exist(self, board, word):
    		que=[]
    		for i in range(len(board)):
    			for j in range(len(board[0])):
    				if board[i][j] ==word[0]:
    					que.append([[i,j]])
    		while que:
    			l=que.pop()
    			current=len(l)
    			if current==len(word):
    				return True
    			result=self.find(board,l,word)
    			if len(result)>0:
    				for i in result:
    					que.insert(0,l+[i])
    		return False
    

Log in to reply
 

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