有人做过leetcode里的word ladder II 吗？

alfonept

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start toend, 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.

自己能写的算法是先用BFS找出每个word离origin多远，然后用类似dfs把路径找出来，没过leetcode OJ的大测试，超时了，不知道有什么比较好的算法做这题？

DWade

这题就看出Python的爽的地方了

source: 我的github https://github.com/jw2013/Leetco ... rd%20Ladder%20II.py

class Solution:
def backtrack(self, result, trace, path, word):
if len(trace[word]) == 0:
result.append([word] + path)
else:
for prev in trace[word]:
self.backtrack(result, trace, [word] + path, prev)
def findLadders(self, start, end, dict):
result, trace, current = [], {word: [] for word in dict}, set([start])
while current and end not in current:
for word in current:
dict.remove(word)
next = set([])
for word in current:
for i in range(len(word)):
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate = word[:i] + j + word[i + 1:]
if candidate in dict:
trace[candidate].append(word)
next.add(candidate)
current = next
if current:
self.backtrack(result, trace, [], end)
return result

复制代码

Shooter_T

iostreamin 发表于 2014-1-21 13:26
得大牛指点，Java通过。

Clear illustration.

Some advice, since it's level-ordered, line 55 & 62 can be deleted...

iostreamin

得大牛指点，Java通过。

public class Solution {
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, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>();
dict.add(start);
dict.add(end);
// init adjacent graph
for(String str : dict){
calcNeighbours(neighbours, str, dict);
}
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
// BFS search queue
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(new Node(null, start, 1));
// BFS level
int previousLevel = 0;
// mark which nodes have been visited, to break infinite loop
HashMap<String, Integer> visited = new HashMap<String, Integer>();
while(!queue.isEmpty()){
Node n = queue.pollFirst();
if(end.equals(n.str)){
// fine one path, check its length, if longer than previous path it's valid
// otherwise all possible short path have been found, should stop
if(previousLevel == 0 || n.level == previousLevel){
previousLevel = n.level;
findPath(n, result);
}else {
// all path with length *previousLevel* have been found
break;
}
}else {
HashSet<String> set = neighbours.get(n.str);
if(set == null || set.isEmpty()) continue;
// note: I'm not using simple for(String s: set) here. This is to avoid hashset's
// current modification exception.
ArrayList<String> toRemove = new ArrayList<String>();
for (String s : set) {
// if s has been visited before at a smaller level, there is already a shorter
// path from start to s thus we should ignore s so as to break infinite loop; if
// on the same level, we still need to put it into queue.
if(visited.containsKey(s)){
Integer occurLevel = visited.get(s);
if(n.level+1 > occurLevel){
neighbours.get(s).remove(n.str);
toRemove.add(s);
continue;
}
}
visited.put(s, n.level+1);
queue.add(new Node(n, s, n.level + 1));
if(neighbours.containsKey(s))
neighbours.get(s).remove(n.str);
}
for(String s: toRemove){
set.remove(s);
}
}
}
return result;
}
public void findPath(Node n, ArrayList<ArrayList<String>> result){
ArrayList<String> path = new ArrayList<String>();
Node p = n;
while(p != null){
path.add(0, p.str);
p = p.parent;
}
result.add(path);
}
/*
* complexity: O(26*str.length*dict.size)=O(L*N)
*/
void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) {
int length = str.length();
char [] chars = str.toCharArray();
for (int i = 0; i < length; i++) {
char old = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) continue;
chars[i] = c;
String newstr = new String(chars);
if (dict.contains(newstr)) {
HashSet<String> set = neighbours.get(str);
if (set != null) {
set.add(newstr);
} else {
HashSet<String> newset = new HashSet<String>();
newset.add(newstr);
neighbours.put(str, newset);
}
}
}
chars[i] = old;
}
}
private class Node {
public Node parent;
public String str;
public int level;
public Node(Node p, String s, int l){
parent = p;
str = s;
level = l;
}
}
}

复制代码

zxyviopond

没做过，随便谈谈自己想法。把dictionary按照是否相连做个图，o(n^2）然后把start和dictionary中每个只差一个字母的连条边,o(n)，end也如此连若干条边 o(n)。
然后BFS？ o(m+n)

不知有没有优化了楼主的算法。

xiaoyangmie

我觉得这题很坑的。。。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母
用O(n^2)的好像就会超时，于是只能对每个单词，枚举与它只有一个字母不同的所有单词，看是否在dict里，这样就是26*l (单词长度) * n * 查dict的时间(认为是常数吧)

大数据应该就能过了。基本算法同LS

imwmwm

careercup上也有貌似

monkeylyf

因为是问最短路径所以是这里dfs不合适用bfs
然后是怎么判断next step. 同时需要用HashMap来记录走过的路径当遇到最短路径的时候根据最后一个词重建整个路径

贴一个java 代码应该可以过test large

public ArrayList<ArrayList<String>> test(String start, String end, HashSet<String> dict) {
HashMap<String, ArrayList<String>> path = new HashMap<String, ArrayList<String>>();
HashMap<String, ArrayList<String>> tmpPath = new HashMap<String, ArrayList<String>>();
Queue<String> curLevel = new LinkedList<String>();
Queue<String> nextLevel = new LinkedList<String>();
curLevel.add(start);
boolean isShortestLevel = false;
while (!curLevel.isEmpty()) {
String str = curLevel.remove();
for (int i = 0; i < start.length(); ++i) {
for(char j = 'a'; j <= 'z'; ++j){
// Change the str then check if the dict contains it.
char[] chs = str.toCharArray();
chs[i] = j;
String oneCharDiff = new String(chs);
if (oneCharDiff.equals(str)) {
continue;
}
if (oneCharDiff.equals(end)) {
isShortestLevel = true; // Reach the shortest path.
}
if (!path.containsKey(oneCharDiff) && dict.contains(oneCharDiff)) {
if (!tmpPath.containsKey(oneCharDiff)) {
ArrayList<String> arr = new ArrayList<String>();
arr.add(str);
tmpPath.put(oneCharDiff, arr);
nextLevel.add(oneCharDiff);
} else {
ArrayList<String> arr = tmpPath.get(oneCharDiff);
arr.add(str);
tmpPath.put(oneCharDiff, arr);
}
}
}
}
if (curLevel.isEmpty()) {
Queue<String> tmp = nextLevel; // Swap nextLevel and curLevel.
nextLevel = curLevel;
curLevel = tmp;
path.putAll(tmpPath); // Move all paths hashed as this level to global path map.
tmpPath = new HashMap<String, ArrayList<String>>(); // tmpPath.clear()
if (isShortestLevel) {
return dfsPath(path, start, end); // Finished with level with shortest path. Start reconstructing path.
}
}
}
return new ArrayList<ArrayList<String>>();
}
public ArrayList<ArrayList<String>> dfsPath(HashMap<String, ArrayList<String>> path, String start, String end) {
// Standord DFS.
ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
ArrayList<String> one = new ArrayList<String>();
one.add(start);
nextPath(path, start, end, all, one, 0);
for (ArrayList<String> i : all) System.out.println(i);
return all;
}

复制代码

zxyviopond

xiaoyangmie 发表于 2013-2-25 15:53
我觉得这题很坑的。。。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母
用O(n^2)的 ...

实现了一下，大数据还是木有过。肿么回事~

xiaoyangmie

zxyviopond 发表于 2013-3-9 02:20
实现了一下，大数据还是木有过。肿么回事~

啊？不应该啊，那你是如何保存还有输出所有结果的呢？

zxyviopond

xiaoyangmie 发表于 2013-3-13 08:32
啊？不应该啊，那你是如何保存还有输出所有结果的呢？

BFS 记录parentnode，找到之后反上去。

xiaoyangmie

zxyviopond 发表于 2013-3-12 23:16
BFS 记录parentnode，找到之后反上去。

这个。。。要不发下代码？

LeoPad

我也是用BFS做了，小数据过了，大数据没过。不知道楼主最后怎么解决的？

[Leetcode] 有人做过leetcode里的word ladder II 吗？

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

浏览过的版块