Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 126] Word Ladder II (Unsolvable)

Question

link

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.

Stats

Frequency 1
Difficulty 1
Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an unsolvable question.

Solution

A solution is available here, but I did not solved it and I gave up.

Code

public class Node {  
    public int dist;  
    public String str;  
    public LinkedList<Node> prev;  

    public Node(int dist, String str) {  
        this.dist = dist;  
        this.str = str;  
        this.prev = new LinkedList<Node>();
    }

    public void addPrev(Node pNode) {  
        prev.add(pNode);  
    }  
}  

public ArrayList<ArrayList<String>> findLadders(String start,  
        String end, HashSet<String> dict) {  
    dict.add(end);  

    // Key: the dictionary string; Value: Node  
    Map<String, Node> map = new HashMap<String, Node>();  
    Queue<String> queue = new LinkedList<String>();  

    Node startNode = new Node(1, start);  
    queue.offer(start);  
    map.put(start, startNode);  

    ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();  

    while (!queue.isEmpty()) {  
        String str = queue.poll();  

        if (str.equals(end)) {  
            getPaths(map.get(end), map, new ArrayList<String>(), ret);  
            return ret;  
        }  

        for (int i = 0; i < str.length(); i++) {  
            for (int j = 0; j <= 25; j++) {  
                // transform it into another word  
                String newStr = replace(str, i, (char) ('a' + j));  

                // if a new word is explored  
                if (dict.contains(newStr)) {  
                    if (!map.containsKey(newStr)) {  
                        // construct a new node  
                        Node node = map.get(str);  
                        Node newNode = new Node(node.dist + 1, newStr);  
                        newNode.prev = new LinkedList<Node>();  
                        newNode.prev.add(node);  

                        map.put(newStr, newNode);  
                        queue.offer(newStr);  
                    } else {  
                        Node node = map.get(newStr);  
                        Node prevNode = map.get(str);  

                        // increase the path set  
                        if (node.dist == prevNode.dist + 1) {  
                            node.addPrev(prevNode);  
                            // queue.offer(newStr); // will cause TLE!!!  
                        }  
                    }  
                }  
            }  
        }  
    }  

    return ret; // return an empty set  
}  

// replace the index of the given string with the given char  
private String replace(String str, int index, char c) {  
    StringBuilder sb = new StringBuilder(str);  
    sb.setCharAt(index, c);  
    return sb.toString();  
}  

// get all the paths by using DFS  
private void getPaths(Node end, Map<String, Node> map,  
        ArrayList<String> curPath, ArrayList<ArrayList<String>> paths) {  
    if (end == null) {  
        paths.add(curPath);  
        return;  
    }  

    curPath.add(0, end.str);  
    if (!end.prev.isEmpty()) {  
        for (Node prevNode : end.prev) {  
            getPaths(prevNode, map, new ArrayList<String>(curPath), paths);  
        }  
    } else {  
        getPaths(null, map, curPath, paths);  
    }  
}