Java Implementation vs. C++ Implementation


  • 5
    Q

    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?


  • 0
    L

    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;
            }
        }
    

  • 0
    Q

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


  • 1
    U

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


  • 0
    Q

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


  • 0
    U

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


  • 0
    S

    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


  • 0
    D
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 3
    M

    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.


  • 19
    C

    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();
    		}
    	}
    }
    

    }


  • 1
    D

    I tried 6 times using Java and finally got it passed without TLE.

    I'm using Dijkstra's algorithm for searching. The trick is to keep the HashSet (dict) for unknown neighbors and maintain a PriorityQueue for known neighbors. Recording the length of the path in the PriorityQueue helps me to get rid of all endless loops. The Dijkstra's algorithm guarantees that minimum necessary words will be visited.


  • 0
    X
    This post is deleted!

  • 0
    F

    I have been working on this problem for a long time and finally figured out a way to solve it in java. My solution consists of three steps:

    1. Start from the starting word to find a list of sets such that the latter of two adjacent sets is a set of words that are one letter different from the former set until you reach the end. If you cannot reach the end, then there is no such ladder to connect the starting word and the ending word.

    2. The list of sets in step one consists of many redundant intermediate words. To speed up, we need to get rid of all these words. The trick is to start from the end now and repeat what we have done in step one. Wheneven we get a set of words that is one letter different from the former set, we retain only the words in this set for the corresponding set we got in step one.

    3. Now we can start building the path using the list of sets obtained in step 2. As pointed by others, it's better to build up the path reversely.

    The following is my code:

    // BFS to find the ladder map -- a list of words for each level;
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
    	List<List<String>> res = new ArrayList<>();
    	LinkedList<String> ls = new LinkedList<>();
        ls.add(end);
        
        if (start.equals(end)) {  
            res.add(ls);
            return res;
        }
        
        Deque<String> queue = new ArrayDeque<>();        
        Set<String> visited = new HashSet<>();
        List<Set<String>> map = new ArrayList<>();
        Set<String> ladder = new HashSet<>();
        
        queue.offerLast(start);
        visited.add(start);
        dict.remove(start);
        
        boolean found = false;
        int currLevel = 1;
        int nextLevel = 0;
        
        while (!queue.isEmpty()) {
            String s = queue.pollFirst();
            ladder.add(s);
            
            for (int i = 0; i < s.length(); i++) {
                StringBuilder sb = new StringBuilder(s);
                char c = 'a';
                
                while (c <= 'z') {
                	sb.setCharAt(i, c++);                	                   
                    String str = sb.toString();
                    if (end.equals(str)) {
                    	found = true;
                    }
                                                           
                    if (!found && dict.contains(str) && !visited.contains(str)) {
                    	queue.offerLast(str);
                        visited.add(str);                                             
                        nextLevel++;
                    }
                }
            }
            
            if (--currLevel == 0) {
            	map.add(ladder);
           	    ladder = new HashSet<>();
            	if (found) {
            		break;
            	}
            	 
            	currLevel = nextLevel;
            	nextLevel = 0;
            }
        }
        
        findLaddersSub(res, map, ls, map.size() - 1);
        return res;
    }
    
    // DFS to get the path reversely -- shortest transformation sequence
    private void findLaddersSub(List<List<String>> res, List<Set<String>> map, LinkedList<String> ls, int i) {
    	if (i == -1) {
    		res.add(ls);
    		return;
    	}
    	
        String s = ls.get(0);       
        for (int j = 0; j < s.length(); j++) {
            StringBuilder sb = new StringBuilder(s);
            char c = 'a';
            
            while (c <= 'z') {
            	sb.setCharAt(j, c++);                	                   
                String str = sb.toString();
                
                if (map.get(i).contains(str)) {
                	LinkedList<String> temp = new LinkedList<>(ls);
                	temp.addFirst(str);
                	findLaddersSub(res, map, temp, i - 1);
                }
            }
        }
    }
    

  • 1
    D

    BFS but with little trick - represent paths as string, so don't need backward traverse, when reach the end (have all path at once):

    /*
     *
     *                            hithotdot
     *   hit --> hithot -->
     *                            hithotlot
     */
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        int n = start.length();
        Set<String> chains = new HashSet<>();
        chains.add(start);
        Map<String, Boolean> repeat = new HashMap<>();
        repeat.put(start, true);
        boolean[] stop = new boolean[1];
    
        while(!stop[0]) {
            chains = getOneEditWords(chains, dict, repeat, stop, n, end);
            for(String chain : chains) {
                repeat.put(chain.substring(chain.length() - n), true);
            }
        }
    
        ArrayList<ArrayList<String>> res = new ArrayList<>();
    
        for(String chain : chains) {
            if(chain.endsWith(end)) {
                ArrayList<String> r = new ArrayList<>();
                for(int i = 0; i <= chain.length() - n; i = i + n) {
                    r.add(chain.substring(i, i + n));
                }
                res.add(r);
            }
        }
    
        return res;
    }
    
    Set<String> getOneEditWords(Set<String> chains, HashSet<String> dict, Map<String, Boolean> repeat, boolean[] stop, int n, String end) {
        Map<String, Set<String>> cache = new HashMap<>();
        Set<String> res = new HashSet<>();
        for(String chain : chains) {
            String lastWord = chain.substring(chain.length() - n);
            Set<String> generated = new HashSet<>();
            if(cache.containsKey(lastWord)) {
                generated = cache.get(lastWord);
            }
            else {
                for(int i = 0; i < lastWord.length(); i++) {
                    char[] wordArray = lastWord.toCharArray();
                    for(char c = 'a'; c <= 'z'; c++) {
                        if(c != lastWord.charAt(i)) {
                            wordArray[i] = c;
                            String gen = new String(wordArray);
                            if(gen.equals(end)) {
                                stop[0] = true;
                            }
                            if(dict.contains(gen) && !repeat.containsKey(gen)) {
                                generated.add(gen);
                            }
                        }
                    }
                }
                cache.put(lastWord, generated);
            }
    
            for(String s : generated) {
                res.add(chain + s);
            }
            
        }
        if (res.isEmpty()){
            stop[0] = true;
        }
        return res;
    }
    

  • 0
    Z

    why can't i get an accepted with bi-directional BFS?can u share ur code with me?


  • 0
    J

    Struggled for long time, finally got acceptted. Use BFS and a linked Node to track the path. The TLE is because of some inefficiency of Java collection library:

    HashSet iteration is 100x slower than ArrayList iteration, ArrayList iteration is again 100X slower than raw array, that's why I copied the dict to dictArray for frequent iteration. That solve the performance issue.

     public class Solution {
    	static class Node{
    		Node parent;
    		String str;
    		Node(Node _parent, String _str){
    			parent = _parent;
    			str = _str;
    		}
    		
    		List<String> generatePath(String end){
    			List<String> result = new ArrayList<String>();
    			for(Node n= this;n != null; n = n.parent)
    				result.add(0, n.str);
    			result.add(end);
    			return result;
    		}
    	}
    	
    	public static List<List<String>> findLadders(String start, String end, Set<String> dict) {
    		dict.remove(start);
    		dict.remove(end);
    		Queue<Node> queue = new LinkedList<Node>();
    		queue.add(new Node(null, start));
    		queue.add(null);  //Level indicator
    		List<List<String>> result = new ArrayList<List<String>>();
    		Set<String> pendingVisited = new HashSet<String>();  //Very important to use set instead of list as it could have repeated items.
    		String[] dictArray = dict.toArray(new String[0]);  //ArrayList has much worse performance than raw Array. 
    		Map<String, List<String>> neihborMap = new HashMap<String, List<String>>();
    		while(!queue.isEmpty()){
    			Node n = queue.poll();
    			if(n == null){
    				if(queue.isEmpty())
    					break;
    				
    				dict.removeAll(pendingVisited);
    				pendingVisited.clear();
    				dictArray = dict.toArray(new String[0]);
    				queue.add(n);
    				if(result.size() > 0)
    					break;
    				continue;
    			}
    			
    			if(isOneLetterChange(n.str, end)){
    				result.add(n.generatePath(end));
    			}else{
    				List<String> nbs = neihborMap.get(n.str);
    				if(nbs == null){
    					nbs = findNeihbors(n.str, dictArray);
    					neihborMap.put(n.str, nbs);
    				}
    				
    				for(String s : nbs){
    					queue.add(new Node(n, s));
    					pendingVisited.add(s);
    				}
    			}
    		}
    		return result;
    	}
    	
    	private static List<String> findNeihbors(String start, String[] dict){
    		List<String> neihbors = new ArrayList<String>();
    		for(String s : dict){
    			if(isOneLetterChange(start, s))
    				neihbors.add(s);
    		}
    		return neihbors;
    	}
    	
    	private static boolean isOneLetterChange(String s1, String s2){
    		boolean hasDiff = false;
    		for(int i=0; i<s1.length(); i++){
    			if(s1.charAt(i) != s2.charAt(i)){
    				if(hasDiff)
    					return false;
    				hasDiff = true;
    			}
    		}
    		return true;
    	}
    }

  • 0
    Q

    Very clear solution. You don't need array btw. Don't iterate over the Set. Optimized findNeighbors function:

    private static List<String> findNeighbors2(String word, Set<String> dict){

    	List<String> list = new ArrayList<String>();
    
    	for(int i=0;i<word.length();i++) {
    
            char[] chars = word.toCharArray();
    
            for(char c = 'a';c<='z';c++) {
    
                chars[i] = c;
    
                String next = new String(chars);
    
                if(dict.contains(next)){
    
                	list.add(next);
    
                }
    
            }
    
        }
    
    	return list;
    
    }

  • 0
    R

    can you say the complexity? if this O(VE)?


Log in to reply
 

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