字梯游戏II

问题

给定两个单词(一个开始,一个结束)和一个字典,找出所有的最短的从开始单词到结束单词的变换的序列(可能不止一个),并满足:

1.每次只能变换一个字母
2.所有的中间单词必须存在于字典中

比如:
输入:

start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]

那么最短的变化序列有两个
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]。
注意:
1. 所有单词的长度都是相同的
2. 所有单词都只含有小写的字母。

分析:
跟之前的字梯游戏相比,这个问题要求求出所有的最短序列,所以要使用一个Prev List来记录前驱节点(可能不止一个)。这样根据这个Prev List就可以遍历出所有的最短组合。

代码如下:

public class WordLadder2 {
private List<List<Integer>> prev;
private String[] allWords;

private boolean canChange(String a, String b) {
int diff = 0;
int len = a.length();
for (int i = 0; i < len; ++i) {
if (a.charAt(i) != b.charAt(i)) {
++diff;
if (diff > 1) {
return false;
}
}
}
return true;
}

private ArrayList<ArrayList<String>> perm(int node) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
String current = allWords[node];
if (node == 0) {
ArrayList<String> as = new ArrayList<String>();
as.add(current);
result.add(as);
} else {
List<Integer> p = prev.get(node);
for (Integer pnode : p) {
ArrayList<ArrayList<String>> subResult = perm(pnode.intValue());
for (ArrayList<String> as : subResult) {
as.add(current);
result.add(as);
}
}
}
return result;
}

public ArrayList<ArrayList<String>> findLadders(String start, String end,
HashSet<String> dict) {
allWords = new String[dict.size() + 2];
int t = 0;
allWords[t++] = start;
for (String d : dict) {
allWords[t++] = d;
}
allWords[t++] = end;
int size = allWords.length;
boolean[][] matrix = new boolean[size][size];
for (int i = 0; i < size; ++i) {
String si = allWords[i];
for (int j = i + 1; j < size; ++j) {
String sj = allWords[j];
if (canChange(si, sj)) {
matrix[i][j] = matrix[j][i] = true;
}
}
}

int[] cost = new int[size];
prev = new ArrayList<List<Integer>>();
for (int i = 0; i < size; ++i) {
cost[i] = Integer.MAX_VALUE;
prev.add(new ArrayList<Integer>());
}
cost[0] = 0;
List<Integer> openlist = new ArrayList<Integer>();
openlist.add(0);
while (!openlist.isEmpty()) {
int current = openlist.remove(openlist.size() – 1);
boolean[] mn = matrix[current];
int cc = cost[current];
for (int i = 0; i < size; ++i) {
if (mn[i]) {
if (cost[i] > cc + 1) {
cost[i] = cc + 1;
prev.get(i).clear();
prev.get(i).add(current);
openlist.add(0, i);
} else if (cost[i] == cc + 1) {
prev.get(i).add(current);
}
}
}
}

if (cost[size – 1] != Integer.MAX_VALUE) {
return perm(size – 1);
} else {
return new ArrayList<ArrayList<String>>();
}
}
}

标签