Java Implementation vs. C++ Implementation

Question

An extremely strange question here...

First I solve this problem with BFS building search graph + DFS build paths. However I tried my best optimizing but got Time Limit Exceeded (I've tried three ways of building path". After profiling, it seems in the building path part, copying ArrayList consumes too much time.

After that I simply "translate" the code into C++ with stl, and got AC easily.

May I know the time limits for these two implementations?

Answer 1

Got AC with Java implementation. When searching in BFS, maintain parent pointer of each node discovered in current level back to parent node in previous level, and finally use DFS to find all path from end to start.

public class Solution {


/* Graph of example:
 *                |--- dot --- dog ---|
 * hit --- hot -- |     |       |     |--- cog
 *                |--- lot --- log ---|
 * 
 * backward adjacent list:
 * hit => null
 * hot => hit
 * dot => hot
 * lot => hot
 * dog => dot
 * log => lot
 * cog => dot -- log
 */
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
     //<String, Queue> contaion all the adjacent words that is discover in its previous level
    HashMap<String, Queue<String>> adjMap = new HashMap<String, Queue<String>>();
    int currLen = 0;
    boolean found = false;
    ArrayList<ArrayList<String>> r = new ArrayList<ArrayList<String>>();//results
    Queue<String> queue = new LinkedList<String>();                     //queue for BFS
    Set<String> unVisited = new HashSet<String>(dict);                  //unvisited words
    Set<String> visitedThisLev = new HashSet<String>();                 //check words visited during same level
    unVisited.add(end);

    queue.offer(start);
    int currLev = 1;
    int nextLev = 0;


    for(String word : unVisited){
        adjMap.put(word, new LinkedList<String>());
    }
    unVisited.remove(start);


    //BFS
    while( !queue.isEmpty() ){
        String currLadder = queue.poll();
        //for all unvisited words that are one character change from current word
        for(String nextLadder : getNextLadder(currLadder, unVisited)){
            if(visitedThisLev.add(nextLadder)) {
                nextLev ++;
                queue.offer(nextLadder);
            }
            adjMap.get(nextLadder).offer(currLadder);
            if(nextLadder.equals(end) && !found) { found = true; currLen+=2;}
        }

        if(--currLev == 0){
            if(found) break;
            unVisited.removeAll(visitedThisLev);
            currLev = nextLev;
            nextLev = 0;
            currLen ++;
        }
    }

    if(found){
        LinkedList<String> p =new LinkedList<String>();
        p.addFirst(end);
        getLadders(start, end, p , r, adjMap, currLen);
    }

    return r;
}

//get all unvisited words that are one character change from current word
private ArrayList<String> getNextLadder(String currLadder, Set<String> unVisited){
    ArrayList<String> nextLadders = new ArrayList<String>();
    StringBuffer replace = new StringBuffer(currLadder);
    for(int i = 0; i < currLadder.length(); i++){
        char old = replace.charAt(i);
        for(char ch = 'a'; ch <= 'z'; ch++){
            replace.setCharAt(i, ch);
            String replaced = replace.toString();
            if(ch != currLadder.charAt(i) && unVisited.contains(replaced) ){
                nextLadders.add(replaced);
            }
        }
        replace.setCharAt(i, old);
    }
    return nextLadders;
}

// DFS to get all possible path from start to end
private void getLadders(String start, String currLadder, LinkedList<String> p, ArrayList<ArrayList<String>> solu, 
                        HashMap<String, Queue<String>> adjMap, int len){
    if(currLadder.equals(start)){
        solu.add(new ArrayList<String> (p));
    }
    else if(len > 0) {
        Queue<String> adjs = adjMap.get(currLadder);
        for(String lad : adjs){
            p.addFirst(lad);
            getLadders(start, lad, p, solu, adjMap, len-1);
            p.removeFirst();
        }
    }
}

}

Answer 2

The key to avoiding TLE, is buliding paths reversely (from end to start).

Comments

I've tried that but got TLE for Java version, too. It is much slower compared to C++.

---

Oh, I think it will be much better, if you divide apart this two stages: searching the end and reversely building paths.

---

I also coded it in Java, and also got TLE. It finished the timeout case on my local machine instantly. Has anyone AC this in Java?

Update: finally AC in Java, it requires aggressive pruning

Answer 3

I also used java, but if I use simple BFS can not be accepted. Then I tried Bi-directional BFS, it could be accepted use Java.

Answer 4

I can' t AC with Java, either. My code is as follow, which only needs BFS and optimizes the code from github.com/mengli/leetcode/blob/master/Word%20Ladder%20II.java

Have you ever solved this problem?

public class Solution {
        public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
            ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
            int currentLevel = 1, nextLevel = 0;
            boolean found = false;
            HashSet<String> visited = new HashSet<String>();
            HashSet<String> sub = new HashSet<String>();
            Queue<String> q = new LinkedList<String>();
            q.add(start);
            Queue<ArrayList<String>> sequences = new LinkedList<ArrayList<String>>();
            ArrayList<String> l = new ArrayList<String>();
            l.add(start);
            sequences.add(l);

            while (!q.isEmpty()) {
                String st = q.remove();
                ArrayList<String> tmp = sequences.remove();
                currentLevel--;
                if (st.equals(end)) {
                    ret.add(tmp);
                    found = true;
                } else {
                    if (!found) {
                        for (int i = 0; i < st.length(); i++) {
                            StringBuffer sb = new StringBuffer(st);
                            for (int j = 0; j < 26; j++) {
                                sb.setCharAt(i, (char) ('a' + j));
                                String next = sb.toString();
                                if (dict.contains(next) && ((!visited.contains(next)) || (sub.contains(next) && visited.contains(next)))) {
                                    q.add(next);
                                    sub.add(next);
                                    visited.add(next);
                                    nextLevel++;
                                    ArrayList<String> nexttmp = new ArrayList<String>(tmp);
                                    nexttmp.add(next);
                                    sequences.add(nexttmp);
                                }
                            }
                        }
                    }
                }
                if (currentLevel == 0) {
                    if (found)
                        break;
                    else {
                        currentLevel = nextLevel;
                        nextLevel = 0;
                    }
                    sub.clear();
                }
            }

            return ret;
        }
    }

Comments

No I haven't solved it yet...I got AC by converting to c++ version.