Also getting TLE in Java...


  • 1
    R

    So I'm getting a TLE on the same test case ("sand", "acne") like the other people. I'm doing BFS, but I don't really get how I can improve the complexity. Do I need to do BFS from both ends at the same time? Any tips? Code:

    public int ladderLength(String start, String end, HashSet<String> dict) {
        Set<String> visited = new HashSet<String>();
        Queue<String> q = new LinkedList<String>();
        Queue<Integer> steps = new LinkedList<Integer>();
        
        int N = start.length();
        q.add(start);
        steps.add(0);
        
        while(!q.isEmpty()){
            String word = q.poll();
            visited.add(word);
            int st = steps.poll();
            char[] wordChar = word.toCharArray();
            
            for(int i = 0; i < N; i++){ // for every character in the word
            	char saved = wordChar[i];
                for(char c = 'a'; c <= 'z'; c++){ // try every char
                    wordChar[i] = c;
                    String str = new String(wordChar); 
                    if(str.equals(end)) return st+1;
                    if(dict.contains(str) && !visited.contains(str)){
                        q.add(str);
                        st++;
                        steps.add(st);
                    }
                }
                wordChar[i] = saved;
            }            
        }
        return 0;
    }

  • 0
    S

    Have you ever read other questions of this problem in the discuss? You are facing the exact same situation like this. Reading the best answer of that question, you will solve yours.


  • 6
    L

    oj.leetcode is really slow now, so I cannot play with your code, but I have a few comments.

    First, you are doing the right algorithm: BFS and you generate all the possible candidates and check if they are in the dictionary. Generating all the candidates is slow (hey, there is 26 letters) but better than testing all the words in the dictionary. (Also you're using a char array instead of manipulating Strings, that's good too)

    I think the main problem is how you handle your set visited. For you visited is, as its name says, the set of all the nodes you have already visited. It means that some words can be inside the Queue q and note inside the Set visited. As a consequence, if a word is the child of the node you're currently visiting, you will add it to the Queue q, even if it is already there. You will visit this node twice then. And everytime you visit this node, you will generate the list of the all the possible children again. And it can be terrible: you will again add to the Queue nodes that are already there… and so on.

    Two quick other remarks, that can affect the performance of your algorithm but more marginally than the "visited problem":

    1. You don't need the Queue steps. You can replace it by 3 variables.
    2. Also the Java Doc suggests that ArrayDeque is faster than LinkedList in most of the cases.

  • 0
    R

    Ah, thank you, that explanation makes sense, I didn't really get the explanation in the other threads, thanks!


  • 0
    W

    thank you, I solve my problem from your code.
    First I search all the dict and check all the word from the source word to those with distance 1,and I got TLE.
    Then I see that you just change the source word with a-z in all position and check if them exist in dict, and I got AC.


Log in to reply
 

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