Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]
As one shortest transformation is "hit" -> "hot" -> "dot" ->
,
"dog" -> "cog"
return its length 5
.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
题目解析:
方案一:图的最短路径问题
可以按照图的方案去做,首先构造一个无向图用来表示单词之间的可达性,然后从表示起点的节点开始对整个图进行BFS遍历,直到找到表示end的节点。按照这个思路也很快写出代码,但是提交后又遇到新问题:不停地超时。
public int ladderLength2(String start, String end, HashSet<String> dict) { if (start == null || end == null || start.equals(end) || start.length() != end.length()) return 0; if (isOneWordDiff(start, end)) return 2; dict.add(start); dict.add(end); String[] dicts = (String[]) dict.toArray(new String[0]); int size = dicts.length; // 表示图的列表数组 ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>(); int s = 0, e = 0; // 判断一个单词一步可以到达哪些单词 for (int i = 0; i < size; i++) { if (start.equals(dicts[i])) s = i; if (end.equals(dicts[i])) e = i; ArrayList<Integer> list = new ArrayList<Integer>(); for (int j = 0; j < size; j++) { if (isOneWordDiff(dicts[i], dicts[j])) list.add(j); } lists.add(list); } HashMap<Integer,Integer> dist = new HashMap<Integer, Integer>(); Queue<Integer> queue = new LinkedList<Integer>(); queue.add(s); dist.put(s, 1); while (!queue.isEmpty()) { int index = queue.poll(); ArrayList<Integer> list = lists.get(index); for (int i = 0; i < list.size(); i++) { if (list.get(i) == e) { return dist.get(index) + 1; } if (!dist.containsKey(list.get(i))) { queue.add(list.get(i)); dist.put(list.get(i), dist.get(index) + 1); } } } return 0; } private boolean isOneWordDiff(String a, String b) { int diff = 0; for (int i = 0; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) { diff++; if (diff >= 2) return false; } } return diff == 1; }
分析一下上面代码的思路:
1.首先将start和end添加到词典中,并将词典转化成数组;
2.创建一个二维数组,二维数组的每一维表示某个单词可以通过一步转化到达的单词,也即利用邻接表的方式存储图结构。在这个过程中也获得了start和end代表的数字;
3.利用构造的图进行BFS遍历,直到遇到end节点或者返回0。在遍历的过程中,由于图的边长是1,所以我们在遍历的时候总是得到从start到某个节点的最短路径,所以我们只需要考虑尚未遍历过的顶点即可。
上述代码是正确的,但是一直超时真是让人搞不清状况。后来,只能上网搜索别人的解答才明白其中的原因。超时的地方不在BFS遍历,而是在我们构造图的地方。我们采用了两层遍历构造一个图,此时复杂度是O(n2),数据量很小时可能体现不出它的劣势,但是当n上千时(给定的测试集中有这样的例子),上面的方法构造图就显得太慢。
这里我们可以不用实际构造图,而在BFS遍历的时候去寻找当前单词可达的下一个单词。如果还是通过遍历所有的单词判断是否可达,则复杂度和上面一样,但实际上在上千个单词中,只有少数几个可以由当前单词一步到达,我们之前的比较浪费了很多时间在不可能的单词上。网上对该问题的解决无一例外都是按照下面的思路:将当前单词每一个字符替换成a~z的任意一个字符,然后判断是否在词典中出现。此时的复杂度是O(26*word_length),当单词比较短时,这种方法的优势就体现出来了。按照这种思路修改后的代码如下:
class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { if(start.size() != end.size()) return 0; if(start.empty() || end.empty()) return 0; queue<string> path; path.push(start); int level = 1; int count = 1; //记录queue中元素的个数,当count==0的时候,level才加加,这个跟层序遍历求深度一样! dict.erase(start);//删除dict中该元素 while(dict.size() > 0 && !path.empty()){ //path非空表示还有路径,如果为空了,就代表不能通过改变一个字符链接到下一个字符 string curword = path.front(); path.pop(); count--; for(int i = 0;i < curword.size();i++){ //一个一个改变curword的字符看是否在dict中,如果在就添加到path中 string tmp = curword; for(char j = 'a';j <= 'z';j++){ if(tmp[i] == j) continue; tmp[i] = j; if(tmp == end) return level+1; if(dict.find(tmp) != dict.end()){ //如果能找到,就将这个单词放入路径中 path.push(tmp); dict.erase(tmp); } } } if(count == 0){ //类似层序遍历的时候计数 count = path.size(); level++; } } return 0; } };
评注:
应该多熟练c++标准库的应用,里面有很多方便的操作供选择。