Why my BFS idea solution got TLE?


  • 0
    H

    My solution got TLE error with "nape" , "mild" case, but I got answer 6 locally. can anybody help me figure out what is wrong with my code? Detail

    public int ladderLength(String start, String end, Set<String> dict) {
     	Deque<String> curr = new ArrayDeque<String>();
    	curr.addLast(start);
    	dict.add(end);
    	int times = 1;
        while(!curr.isEmpty() && !curr.contains(end)){
       // here use two queues one record current level and one record next level, 
       // each time updating curr with next,  times add 1
    		Deque<String> next = new ArrayDeque<String>();
    		for(String currs: curr){
    			for(String s: dict){
    				if ( distance(currs, s) == 1) {
    					next.addLast(s);
    				}
    			}
                                // remove elements in curr from dict to save time 
    			for(String s : next){
    				if (dict.contains(s)){
    					dict.remove(s);
    				}
    			}
    		}
    		curr = next;
    		times++;
    	}
    	if (curr.isEmpty()) return 0;
    	else return times;
    }
    
    //calculate distance between two strings
    private int distance(String a, String b){                    
        int result = 0;
        for(int i = 0; i < a.length(); i ++){
            result += (a.charAt(i) == b.charAt(i))? 0:1;
        }
        return result;
    }

  • 0
    H

    After reformating dict to dictt with HashMap, it is accepted, Does it because the dict.contains(s) and dict.remove(s) need O(n) time, while HashMap need O(logn) time?


Log in to reply
 

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