Why my code is TLE, I have checked it for many times but cannot get the answer


  • 0
    E
    public int ladderLength(String start, String end, Set<String> dict) {
    
        int length = 1;
    
        LinkedList<String> queue = new LinkedList<String>();
    
        HashSet<String> detected = new HashSet<String>();
    
        queue.add(start); detected.add(start);
    
        String last = start;
    
        while(!queue.isEmpty()){
    
            String tempS = queue.pop();
    
            for (int i = 0; i < tempS.length(); i++){
    
                for (char c = 'a'; c <='z'; c++){
    
                    String s = tempS.substring(0,i)+c+tempS.substring(i+1,tempS.length());
                    
    
                    if (detected.contains(s))
                        continue;
                    else
                        detected.add(s);
    
                    if (s.equals(end))
                        return length+1;
                    else{
                        if (dict.contains(s)){
                            queue.add(s);
                        }
                    }
                }
            }
    
            if (tempS.equals(last)){
                last=queue.peekLast();
                length++;
            }
        }
    
        return 0;
    
    }

  • 0
    S

    Hi, I suggest instead of using substring and "+" operations, using the char array may help.

    for (int i = 0; i < len; i++) {
    	char saved = tmp[i];
    	for (char cur = 'a'; cur <= 'z'; cur++) {
    		tmp[i] = cur;
            String changed = new String(tmp);
            if (changed.equals(end))
                 return level+1;
            if (visited.containsKey(changed) &&  !visited.get(changed)) {
                levels.add(changed);
                visited.put(changed, true);
                nextNum++;
            }
    	}
    	//remember to change the char back
    	tmp[i] = saved;
    }
    

  • 0
    E

    I also used char array before, but it told me memory exceeds limitation. I tried you suggestion and my code today, both work fine today now. Interesting, maybe there were problem on the server. Anyway, thanks for your help.


Log in to reply
 

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