Why my code got TLE??????


  • 0
    C

    I got accepted code at the first time. And i revised it then got TLE. I don't understand why because the two version actual have the same thoughts but diff implementation.

    public class Solution {

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        if(start==null || end==null || start.length() != end.length()){
            return null;
        }
        List<List<String>> res=new ArrayList();
        Queue<String> queue = new LinkedList();
        HashMap<String,List<String>> parents = new HashMap();
        queue.add(start);
        dict.add(end);
        while(queue.size() > 0){
            int size = queue.size();
            Set<String> cur_level = new HashSet();
            for(String cur_level_node : queue){
            	cur_level.add(cur_level_node);
            }
            for(int i=0;i<size;i++){
                String cur = queue.poll();
                if(cur.equals(end)){
                    getRes(res,parents,end);
                    return res;
                }
                char[] arr=cur.toCharArray();
                for(int j=0;j<arr.length;j++){
                    for(arr[j]='a';arr[j]<='z';arr[j]++){
                        String tmp=String.valueOf(arr);
                        if(dict.contains(tmp) && !cur_level.contains(tmp)){
                            queue.add(tmp);
                            List<String> p = parents.get(tmp);
                            if(p==null){
                                p=new LinkedList();
                            }
                            p.add(cur);
                            parents.put(tmp,p);
                        }
                    }
                    arr[j]=cur.charAt(j);
                }
            }
            for(String cur_level_node : cur_level){
            	dict.remove(cur_level_node);
            }
        }
        return res;
    }
    
    private void getRes(List<List<String>> res,Map<String,List<String>> parents,String end){
        List<String> temp = new LinkedList();
        getRes(res,parents,end, temp);
    }
    
    private void getRes(List<List<String>> res,Map<String,List<String>> parents,String root,List<String> temp){
            List<String> p = parents.get(root);
            if(p==null){
                temp.add(root);
                List<String> temp_res = new LinkedList();
                for(int i=temp.size()-1;i>=0;i--){
                    temp_res.add(temp.get(i));
                }
                res.add(temp_res);
                temp.remove(root);
                return;
            }
            temp.add(root);
            for(int i=0;i<p.size();i++){
                getRes(res,parents,p.get(i), temp);
            }
            temp.remove(temp.size()-1);
    }
    

    }


  • 0
    D

    Because you're using LinkedList. LinkedList "get" operation works in O(n) time, try using ArrayList instead. Although I didn't dive deep into your code, that's the first thing I notice. Hope this helps


Log in to reply
 

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