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.

####Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

##解题思路
该题是一个寻找字符串中最短路径的问题,我们可以把它转变成图来求解。我们先给题目进行图的映射,顶点则是每个字符串,然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个方法的优势,注意到我们的字符集只有小写字母,而且字符串长度固定,假设是L。那么可以注意到每一个字符可以对应的边则有25个(26个小写字母减去自己),那么一个字符串可能存在的边是25*L条。接下来就是检测这些边对应的字符串是否在字典里,就可以得到一个完整的图的结构了。根据题目的要求,等价于求这个图一个顶点到另一个顶点的最短路径,一般我们用广度优先搜索即可。

下面的代码框架整体上是一个图的广度优先搜索问题,只不过在判断边的时候需要改变字符,并判断是否在字典中。

##算法代码
代码采用JAVA实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
if(start==null || end==null || dict==null || start.length()==0 || end.length()==0 || start.length()!=end.length())
return 0;
//把这道题抽象为图中寻找最短路径长度的问题,可以采用图的广度优先遍历
LinkedList<String> queen=new LinkedList<String>();//定义队列
HashSet<String> isVisited=new HashSet<String>();//定义已经访问过的节点
int level=1;//定义当前的层级
int curNum=1;//定义当前一层的节点数
int nextNum=0;//定义下一层的节点数
queen.offer(start);
isVisited.add(start);
while(!queen.isEmpty())
{
String str=queen.poll();
curNum--;
//去寻找和该节点可能差一个字母的所有单词
for(int i=0;i<str.length();i++)
{
char[] charStr=str.toCharArray();
//对每一个字符进行设定,判断是否存在这个单词
for(char a ='a';a<='z';a++) //这里其实包含了其自身
{
charStr[i]=a;
String gstr=new String(charStr);
if(gstr.equals(end)) //找到了end 单词,返回最短路径,即最短层级
return level+1;
if(dict.contains(gstr) && !isVisited.contains(gstr))
{
nextNum++;
queen.offer(gstr);
isVisited.add(gstr);
}
}
}
if(curNum==0) //说明该层访问结束,需要进入下一层
{
curNum=nextNum;
nextNum=0;
level++;
}
}
return 0;
}
}

Comments