Word Ladder II | Leetcode

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

Solution: https://leetcode.com/discuss/9523/share-two-similar-java-solution-that-accpted-by-oj

Algorithm 1: Slow (Will Not Pass Leetcode)

public class Solution {
    private static class WordNode {
        private final String word;
        private final int cost;
        private final WordNode prev;
        
        private WordNode(String word, int cost, WordNode prev) {
            this.word = word;
            this.cost = cost;
            this.prev = prev;
        }
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> answer = new ArrayList<>();
        LinkedList<WordNode> queue = new LinkedList<>();
        queue.addLast(new WordNode(start, 1, null));
        dict.remove(start);
        int minCost = 0;
        
        do {
            WordNode node = queue.removeFirst();
            if (minCost != 0 && node.cost > minCost) break;
            
            char[] a = node.word.toCharArray();
            for (int i = 0; i < a.length; i++) {
                char ch = a[i];

                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == ch) continue;
                    a[i] = c;
                    String s = new String(a);
                    if (s.equals(end)) {
                        if (minCost == 0 || node.cost == minCost) {
                            answer.add(formResult(node, end));
                            minCost = node.cost;
                            continue;
                        }
                    }
                    if (!dict.contains(s)) continue;
                    queue.addLast(new WordNode(s, node.cost + 1, node));
                }
                
                a[i] = ch;
            }
        } while (!queue.isEmpty());
        
        return answer;
    }
    
    private static List<String> formResult(WordNode node, String end) {
        LinkedList<String> list = new LinkedList<>();
        list.addFirst(end);
        while (node != null) {
            list.addFirst(node.word);
            node = node.prev;
        }
        return list;
    }
}

Algorithm 2: Fast (Will Pass Leetcode)

public class Solution {
    private List<List<String>> answer = new ArrayList<List<String>>();
    private LinkedList<String> backTraceList = new LinkedList<String>();
    private Map<String, List<String>> adjacentWordsMap = new HashMap<String, List<String>>();

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        int curr = 1;
        int next = 0;
        boolean found = false;

        LinkedList<String> queue = new LinkedList<>();
        Set<String> unvisited = new HashSet<String>(dict);
        Set<String> visited = new HashSet<String>();

        queue.add(start);
        unvisited.add(end);
        unvisited.remove(start);

        do {
            String word = queue.removeFirst();
            curr--;
            char[] a = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                char savedChar = a[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (unvisited.contains(newWord)) {
                        // Key statement - avoid duplicate queue insertion.
                        if (!visited.contains(newWord)) {
                            visited.add(newWord);
                            next++;
                            queue.addLast(newWord);
                        }

                        // Build adjacency graph.
                        List<String> list = adjacentWordsMap.get(newWord);
                        if (list == null) {
                            list = new LinkedList<String>();
                            adjacentWordsMap.put(newWord, list);
                        }
                        list.add(word);

                        if (newWord.equals(end)) found = true;
                    }
                }
                a[i] = savedChar;
            }
            
            if (curr == 0) {
                if (found) break;
                curr = next;
                next = 0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        } while (!queue.isEmpty());

        backTrace(end, start);

        return answer;
    }

    private void backTrace(String word, String start) {
        if (word.equals(start)) {
            backTraceList.addFirst(start);
            answer.add(new ArrayList<String>(backTraceList));
            backTraceList.removeFirst();
            return;
        }
        backTraceList.addFirst(word);
        if (adjacentWordsMap.containsKey(word)) {
            for (String s : adjacentWordsMap.get(word)) {
                backTrace(s, start);
            }
        }
        backTraceList.removeFirst();
    }
}