Word Ladder

 

Word Ladder

 

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Naive way: 第一想法是BFS。但这题好像是Dijkstra算法 的典型。仔细想了想，BFS是每一次将与目标为邻的word 压进队列，最多有 n个邻居，（n是字典的大小）。那么BFS的算法复杂度就是O(n^2)，如果考虑到是对字符的处理，最多有26种变化，每个位置都替换一次是O(k), (k是word的长度），那么算法复杂度就是O(nk).一般情况下，O(k) << O(n)，而且，替换单个字符去主动匹配 比 对字典中每一个word进行遍历 要高效的多。两种的space complexity都是O(n)。

那么Dijkstra呢。我们首先需要构建一个图，保存整个字典的信息，这首先需要O(n)空间，然后构建图需要O(n^2)的遍历。运行Dijikstra算法需要O(n^2)的run time。

最关键的是这道题只要求输出步长，不要求中间节点的信息，所以BFS更优。后面有个这道题的变形要求输出每一步的word，可能Dijkstra会更实用。最重要的一点是，这里每一个节点之间的距离都是1，用Dijkstra最后会变成BFS。


// 用了一个Map去存层数，并使用原字典是Set的特性，每次遍历过的直接从字典中删除。

**我曾经想过会不会出现这种情况**
hit->hot->...-> cog
cot->hot->..-> cog
如果一开始hot在hit后面遍历掉被删除出字典，等到遍历cot的邻居就没有hit了。这种情况写出来就很明了。
Because                         layer(hit) <= layer(cot)
And       steps(hot to cog | start from hit) = step(hot to cog | start from cot)
Thus      layer(cog | going through hit) <= layer(cog | going through cot).



public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        // BFS
        Map<String, Integer> layers = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();
        queue.add(start);
        layers.put(start,1);
        while(!queue.isEmpty()){
            String s = queue.poll();
            int layer = layers.get(s);
            for(int i = 0;i < s.length();i++){
                for(char c = 'a'; c <= 'z';c++){
                    String temp = s.substring(0,i) + c + s.substring(i+1,s.length());
                    if(temp.equals(end))
                        return layer+1;
                    if(dict.contains(temp)){
                        queue.add(temp);
                        layers.put(temp,layer+1);
                        dict.remove(temp);
                    }
                }
            }
        }
        return 0;
    }
}