Word Ladder II

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

Only one letter can be changed at a time
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.
这道题很难,不是难在算法而是他的time limit要求太紧,似乎C++的实现要更快一些,java慢一些所以更难。试了很多种办法,只有最后一种通过了。
因为这题问的是输出所有答案,所以想当然用recursion办法,但是我们不知道最短path是多少, 所以只好输出所有结果以后再找,这样显然效率很低,下面的code被OJ报Time Exceed Limit

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        HashSet<String> visited = new HashSet<String>();
        visited.add(start);
        ArrayList<ArrayList<String>> res = findNext(start, end, dict, visited); 
        int minLength = Integer.MAX_VALUE;
        if (res.isEmpty())
            return res;
        for (ArrayList<String> l : res)
        {
            if (l.size() < minLength);
                minLength = l.size();
        }
        for (ArrayList<String> l :res)
        {
            if (l.size() > minLength)
                res.remove(l);
        }
        for (ArrayList<String> l :res)
        {
            l.add(0, start);
        }
        return res;
    }
    
    public ArrayList<ArrayList<String>> findNext(String s, String end, HashSet<String> dict, HashSet<String> visited)
    {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        for (int i = 0; i < s.length(); i++)
        {
            char [] t = s.toCharArray();
            for (char c = 'a'; c <= 'z'; c++)
            {
                t[i] = c;
                String next = new String(t);
                if (next.equals(end)) // if found the result
                {
                    ArrayList<String> l = new ArrayList<String>();
                    l.add(next);
                    res.add(l);
                    return res;
                }
                if (dict.contains(next) && !visited.contains(next))
                {
                    visited.add(next);
                    HashSet<String> nextVisited = new HashSet<String>(visited);
                    if (findNext(next, end, dict, nextVisited).isEmpty())
                        continue;
                    else
                    {
                        for(ArrayList<String> list : findNext(next, end, dict, nextVisited))
                        {
                             list.add(0, next);
                             res.add(list);
                        }
                    }
                }
            }
        }
        return res;
    }
}

所以还是要用Word Ladder I中的BFS的方法来解决,等找出结束词之后,再通过DFSbacktrack找出所有路径。
我们用一个HashMap来map当前词和发现当前词的上一层的词(可能有多个,用hashset来存),不仅如此,我们还要记录每个node的层数,不然的话会加入很多不必要的词(在之前的层出现过,如果再出现,那肯定不是最短距离,这样的词会增加许多overhead,导致time limit exceeded)
然后通过DFS的方法从end开始将所有的词重构出来。
要注意start要放进去visited里,map里不需要,因为start本身没有上一层。
似乎是hashmap的查找overhead更多,没有最后一种用pointer的快,还是会exceed time limit。

public class Solution {      
    ArrayList<ArrayList<String>> answer = new ArrayList<ArrayList<String>>();  
    
    public void findPath(String end, LinkedList<String> cur, String start, HashMap<String, LinkedList<String>> map) {  
        if (end.equals(start)) { 
            ArrayList<String> temp = new ArrayList<String>(cur);
            answer.add(temp);  
            return;  
        }  
        LinkedList<String> temp;  
        for (String s : map.get(end)) {  
            temp = new LinkedList<String>(cur);  
            temp.add(0, s);  
            findPath(s, temp, start, map);  
        }  
    }  
      
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {  
        // Start typing your Java solution below  
        // DO NOT write main() function  
        HashMap<String, LinkedList<String>> map = new HashMap<String, LinkedList<String>>();  
        HashMap<String, Integer> visited = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();
        visited.put(start, 1);
        int level = 0;
        queue.add(start);  
        boolean stop = false;  
        while (queue.size() > 0 && !stop) {  
            int count = queue.size(); // track no of nodes in curr level
            level++;
            for (int i = 0; i < count; i++) {  
                String curr = queue.poll();  
                for (int j = 0; j < curr.length(); j++) {  
                    StringBuilder t = new StringBuilder(curr);  
                    for (char k = 'a'; k <= 'z'; k++) {  
                        t.setCharAt(j, k);  
                        String next = t.toString();
                        if (dict.contains(next) && !next.equals(curr)) {  
                            if (visited.get(next) == null) // never visited 
                            {
                                LinkedList<String> temp = new LinkedList<String>();
                                temp.add(curr);
                                map.put(next, temp);
                                visited.put(next, level + 1);
                                queue.add(next);
                            }
                            else if (visited.get(next) == level + 1) // if visited but in the same level
                            {
                                map.get(next).add(curr);
                                queue.add(next);
                            } // if visited in the previous level, no need to consider again
                            if (next.equals(end))
                            {
                                stop = true;
                            }
                        }  
                    }  
                }  
            }  
        }  
        
        if (stop) // if found the result, other wise nothing found
        { 
            findPath(end, new LinkedList<String>(Arrays.asList(end)), start, map);  
        }  
        return answer;  
    }  
} 

还有一种方法是用一个新的class Node来追踪,每个Node存一个hashset,指向之前一层发现自己的node,其实原理和之前的hashset是一样的。也是要注意每个node要记录层数,不然会加入不必要的node导致时间超过。

    class Node {  
        int no;  
        String val;  
        LinkedList<Node> prev;      
          
        Node(int no, String v) {  
            this.no = no;  
            this.val = v;  
        }  
          
        void addPrev(Node pNode) {  
            if (prev == null) {  
                prev = new LinkedList();  
            }  
            prev.add(pNode);  
        }  
    }  

    
    ArrayList<ArrayList<String>> answer = new ArrayList<ArrayList<String>>();  
      
    public void findPath(Node node, ArrayList cur, String start) {  
        if (node.val.equals(start)) {  
            answer.add(cur);  
            return;  
        }  
        ArrayList temp;  
        for (Node n : node.prev) {  
            temp = new ArrayList(cur);  
            temp.add(0, n.val);  
            findPath(n, temp, start);  
        }  
    }  
      
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet dict) {  
        HashMap<String, Node> map = new HashMap();  
        Queue<Node> queue = new LinkedList();  
        Node node = new Node(0, start);  
        Node endNode = null;  
        map.put(start, node);  
        queue.add(node);  
        boolean stop = false;  
        while (queue.size() > 0 && !stop) {  
            int count = queue.size();  
            for (int i = 0; i < count; i++) {  
                node = queue.poll();  
                for (int j = 0; j<node.val.length(); j++) {  
                    StringBuilder t = new StringBuilder(node.val);  
                    for (char k = 'a'; k <= 'z'; k++) {  
                        t.setCharAt(j, k);  
                        if (dict.contains(t.toString())) {  
                            Node v = map.get(t.toString());  
                            if (v == null) {  
                                Node temp = new Node(node.no + 1, t.toString());  
                                temp.addPrev(node);  
                                queue.add(temp);  
                                map.put(t.toString(), temp);  
                                if (t.toString().equals(end)) {  
                                    endNode = temp;  
                                    stop = true;  
                                }  
                            }  
                            else {  
                                if (v.no == node.no + 1) {  
                                    v.addPrev(node);  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }   
        if (endNode != null) {  
            findPath(endNode, new ArrayList(Arrays.asList(end)), start);  
        }  
        return answer;  
    } 

This is to use hashMap to keep track of the word that came from. Notice we put only those that has been popped out of the fifo into the visited set because one word could come from multiple word from last level. So visited should only contain those that is above current level.

The following code works correctly but the OJ reports time limit exceeded


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s