Similar approach got accepted in Word Ladder I, but TLE here


  • 0
    Z
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
        Queue<String> stringQueue = new LinkedList<String>();
        Queue<ArrayList<String>> listQueue = new LinkedList<ArrayList<String>>();
        //HashSet<String> visited = new HashSet<String>();
        stringQueue.add(start);
        ArrayList<String> cur = new ArrayList<String>();
        cur.add(start);
        listQueue.add(cur);
        int minDis = -1;
        while(!stringQueue.isEmpty()){
            cur = listQueue.poll();
            String s = stringQueue.poll();
            //HashSet<String> curSet = setQueue.poll();
            if(s.equals(end)){
                if(minDis == -1 || cur.size() == minDis){
                    list.add(cur);
                    minDis = cur.size();
                }
                if(cur.size() > minDis){
                    return list;
                }
            }
            //HashSet<String> tmp = new HashSet<String>();
            for(int i = 0; i < s.length(); i++){
                char[] c = s.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){
                    c[i] = j;
                    String nS = new String(c);
                    if(dict.contains(nS) && !s.equals(nS)){
                        //tmp.add(nS);
                        ArrayList<String> nlist = new ArrayList<String>();
                        nlist.addAll(cur);
                        nlist.add(nS);
                        listQueue.add(nlist);
                        stringQueue.add(nS);
                    }
                    
                }
            }
        }
        return list;
    }
    

    The code is almost identical to my Word Ladder I code. In Ladder I I used a queue to store distance, while here I'm using a queue to store ArrayLists. The only possible place that increased time complexity is when I adding the current array with the new String to the queue.

    I first create a copy of the current ArrayList, then add the next String to it, then push it into the queue. Maybe copying the array is too expensive, but is there a better way out of it?


Log in to reply
 

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