Posted on 2013-04-18 12:46
小明 阅读(1505)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
分析：
这个问题本质是一个图论中的寻求最短路径的问题。之前做过一个迷宫寻路的demo，有兴趣的可以看看：
http://slab.sinaapp.com/pathfinder/为了提高效率，把输入的HashSet转化成数组来处理，并预先计算好他们相互的关系。下面使用的算法是BFS，在大多数情况下，都是足够快的。如果要优化，可以使用A*，但是实现的复杂度就会大幅增加。
代码如下：
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;
}
}