Posted on 2013-04-18 17:32
小明 閱讀(1373)
評論(0) 編輯 收藏 所屬分類:
數據結構和算法
分析：
跟之前的
字梯游戲相比，這個問題要求求出所有的最短序列，所以要使用一個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>>();
}
}
}