Posted on 2013-04-18 12:46
小明 閱讀(1518)
評論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
這個問題本質(zhì)是一個圖論中的尋求最短路徑的問題。之前做過一個迷宮尋路的demo，有興趣的可以看看：
http://slab.sinaapp.com/pathfinder/為了提高效率，把輸入的HashSet轉(zhuǎn)化成數(shù)組來處理，并預先計算好他們相互的關(guān)系。下面使用的算法是BFS，在大多數(shù)情況下，都是足夠快的。如果要優(yōu)化，可以使用A*，但是實現(xiàn)的復雜度就會大幅增加。
代碼如下：
public class WordLadder {
private boolean canChange(char[] a,char[] b){
int diff = 0;
int len = a.length;
for(int i=0;i<len;++i){
if(a[i]!=b[i]){
++diff;
if(diff>1){
return false;
}
}
}
return true;
}
public int ladderLength(String start, String end, HashSet<String> dict) {
Object[] all = new Object[dict.size()+2];
int t=0;
all[t++]=start.toCharArray();
for(String d:dict){
all[t++]=d.toCharArray();
}
all[t++]=end.toCharArray();
int size = all.length;
boolean[][] matrix = new boolean[size][size];
for(int i=0;i<size;++i){
char[]si = (char[])all[i];
for(int j=i+1;j<size;++j){
char[] sj = (char[])all[j];
if(canChange(si,sj)){
matrix[i][j] = matrix[j][i] = true;
}
}
}
int[] cost = new int[size];
for(int i=0;i<size;++i){
cost[i] = Integer.MAX_VALUE;
}
cost[0] = 0;
List<Integer> openlist = new ArrayList<Integer>();
openlist.add(0);
int target = size-1;
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(i==target){ //find
return cc+2;
}
if(cost[i]>cc+1){
cost[i]=cc+1;
openlist.add(0,i);
}
}
}
}
return 0;
}
}