TLE error, but passed once


  • 0
    J

    Here is the solution of mine. It passed the test once and I resubmitted it, it won't pass again. And a TLE error is given. The basic idea of this algorithm is http://www.cs.cmu.edu/~adamchik/15-121/labs/HW-4 Word Ladder/lab.html

    Pleas help optimize the code or give me some advices. Thank you very much

       public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dic) {
        //result stores the final return value
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        dic.remove(start);
        dic.add(end);
        //queue stores the stacks which hold the word ladders
        Queue<Stack<String>> queue = new LinkedList<Stack<String>>();
        Stack<String> stack = new Stack<String>();
        String compare = null;
        stack.push(start);
        queue.add(stack);
    
        ArrayList<String> removeCollection = new ArrayList<String>();
        ArrayList<String> usedCollection = new ArrayList<String>();
        int preLength = 1;
        while(!queue.isEmpty()){
            Stack<String>  stack1 = queue.poll();
            compare = stack1.peek();
            if(compare.equals(end)){
                if((result.isEmpty() || stack1.size() == result.get(0).size())){
                    ArrayList<String> arrayList = new ArrayList<String>(stack1);
                    result.add(arrayList);
                    continue;
                }
                else
                    break;
            }
    
            //when handle another layer
            int currentLength = stack1.size();
            if(currentLength > preLength){
                preLength = currentLength;
                for(String item: removeCollection){
                    dic.remove(item);
                }
                removeCollection.clear();
            }
    
            int stringLength = compare.length();
    
            String createString;
            for(int i = 0; i < stringLength; i++){
                char [] arr = compare.toCharArray();
                for(char c = 'a'; c < 'z'; c++){
                    arr[i] = c;
                    createString = new String(arr);
                    if(dic.contains(createString)){
                        Stack<String> tempStack = new Stack<String>();
                        tempStack.addAll(stack1);
                        tempStack.add(createString);
                        queue.add(tempStack);
                        removeCollection.add(createString);
                    }
                }
            }
        }
        return result;
    }

Log in to reply
 

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