BFS Solution - Word Ladder II

The basic idea is to BFS parse all possible Strings. create a process ing queue… and save the processed String…Process by levels… The purpose for level in the solution below is to ONLY count the current level (first for loop) if end has reached (exit second forLoop immediately since one letter one match, not necessary to try all 26s)… if reached, exit all loop(while layer)…

The tricky part is to save parent for each String as a list… so when end reached… loop and recurse all parent lists to reach the solution…. which could be a separate question based on its complexity… Be careful in Java as clean (remove(0)) will affect all list if you add the list directly… To separate the reference, create a clone list each time…

A queue, a map, a dict set, a level parse set, a processed set, a recursive… a BFS… a boolean for found…a levelSize count...

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        if(start == null || end == null || start.length() != end.length() || start.equals(end)){
            return results;
        }
        Queue<String> processin = new LinkedList<String>();
        HashSet<String> processed = new HashSet<String>();
        HashSet<String> levelNodes = new HashSet<String>();
        Map<String, ArrayList<String>> parents = new HashMap<String, ArrayList<String>>();
        processin.offer(start);
        int levelSize = processin.size();
        boolean isFound = false;
        while(!processin.isEmpty()){
            String cur = processin.poll();
            levelSize--;
            for(int i = 0; i < cur.length(); i++){
                StringBuilder sb = new StringBuilder(cur);
                for(char lp = 'a'; lp <= 'z'; lp++){
                    if(lp == cur.charAt(i)){
                        continue;
                    }
                    sb.setCharAt(i, lp);  
                    if(sb.toString().equals(end)){
                        isFound = true;
                        if(parents.containsKey(end)){
                            parents.get(end).add(cur);
                        }else{
                            ArrayList<String> newParents = new ArrayList<String>();
                            newParents.add(cur);
                            parents.put(end, newParents);
                        }
                        break;
                    }
                    if(dict.contains(sb.toString()) && !processed.contains(sb.toString())){
                        levelNodes.add(sb.toString());
                        if(parents.containsKey(sb.toString())){
                            parents.get(sb.toString()).add(cur);
                        }else{
                            ArrayList<String> newParents = new ArrayList<String>();
                            newParents.add(cur);
                            parents.put(sb.toString(), newParents);
                        }
                    }
                }
                sb = new StringBuilder(cur);
            }
            if(levelSize == 0){
                if(isFound){
                    calculatePath(results, end, start, parents, new ArrayList<String>());
                    break;
                }
                for(String loop : levelNodes){
                    processin.offer(loop);
                    processed.add(loop);
                }
                levelSize = processin.size();
                levelNodes.clear();
            }
        }
        return results;
    }
   
    private void calculatePath(ArrayList<ArrayList<String>> results, String start, String end, Map<String, ArrayList<String>> parents, ArrayList<String> candidate){
        candidate.add(0, start);
        if(start.equals(end)){
            ArrayList<String> clonePath = new ArrayList<String>();
            clonePath.addAll(candidate);
            results.add(clonePath);
        }else{
            for(String lp : parents.get(start)){
                calculatePath(results, lp, end, parents, candidate);
            }
        }
        candidate.remove(0);
    }
}