[LeetCode-JAVA] Word Ladder II
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode-JAVA] Word Ladder II，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3134字，纯文字阅读大概需要5分钟。
内容图文
题目：
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"]
]
思路：先建立dict的邻接链表，例子中的结果如下：
hit : [hot]
cog : [dog, log]
hot : [hit, lot, dot]
lot : [hot, log, dot]
dog : [cog, log, dot]
log : [cog, lot, dog]
dot : [lot, hot, dog]
在Word LadderI的基础上，由于要重新构建结果集，因此要自己创建一个Node类，保存每一个节点的上一个节点，这样在找到最短结果的时候，以此找到该节点的上一个节点，加入链表即可。
需要注意的几点：
（1）构建邻接链表前，需要把start和end加入，这样才能找到结果。
（2）构建邻接链表的时候，对于每一个单词，一定要在每一次替换char后，再将其恢复，以便进行下一次判断。
（3）每一层的queue用一个num来记录此层的Node个数，只要是找到一个，就证明这一层即为最短路径，设标志位为true，将该层循环之后，结束循环。
（4）循环的过程中，需要判断节点是否已经被判断过，创建一个Set用于记录所有判断过的节点。
代码：
public
class
Solution {
private
class
Node{
public
Node pre;
public
String val;
public
Node(Node p, String s){
pre = p;
val = s;
}
}
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
dict.add(start);
dict.add(end); //注意（1）
Map<String, Set<String>> neighbours = calNeighbours(dict);
List<List<String>> req = new ArrayList<List<String>>();
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(new Node(null, start)); //开始节点的前一个为null
Set<String> visited = new HashSet<String>(); //注意（4）boolean flag = false; //注意（3）while(!queue.isEmpty() || visited.size() == dict.size()){
int num = queue.size();
for(int i = 0 ; i < num ; i++){
Node n = queue.poll();
if(end.equals(n.val)){
findPath(n, req);
flag = true; //注意（3）
}else{
Set<String> temp = neighbours.get(n.val);
if(temp == null || temp.size() == 0)
continue;
else{
for(String s : temp){
if(!visited.contains(s)){ //注意（4）
queue.offer(new Node(n, s));
}
}
}
}
visited.add(n.val);//注意（4） }
if(flag)
break;
}
if(!flag) // 如果flag为false，证明无解returnnew ArrayList<List<String>>();
return req;
}
privatevoid findPath(Node n, List<List<String>> req) {
// TODO Auto-generated method stub
List<String> temp = new ArrayList<String>();
while(n != null){
temp.add(0, n.val);
n = n.pre;
}
req.add(temp);
}
public Map<String, Set<String>> calNeighbours(Set<String> dict) {
Map<String, Set<String>> neighbours = new HashMap<String, Set<String>>();
for(String str : dict){
int len = str.length();
char[] chars = str.toCharArray();
for(int i = 0 ; i < len ; i++){
char old = chars[i]; //注意（2）for(char c = ‘a‘ ; c <= ‘z‘ ; c++){
if(c == chars[i])
continue;
chars[i] = c;
String newstr = new String(chars);
if(dict.contains(newstr)) {
Set<String> set = neighbours.get(str);
if(set != null)
set.add(newstr);
else{
Set<String> newset = new HashSet<String>();
newset.add(newstr);
neighbours.put(str, newset);
}
}
chars[i] = old ; //注意（2）引用型变量 每一次用完要还原
} // end fot c
} // end for len
} // end for strreturn neighbours;
}
}
AC时间为 1120ms左右，因此还有很大的改进空间，继续新的思路。
原文：http://www.cnblogs.com/TinyBobo/p/4575009.html
内容总结
以上是互联网集市为您收集整理的[LeetCode-JAVA] Word Ladder II全部内容，希望文章能够帮你解决[LeetCode-JAVA] Word Ladder II所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。