i*********7
发帖数: 348 | 1 这一题大部分人应该都知道是用BFS解。
我只是想自己试验一下DFS的解。
DFS解如果要避免TLE，重点在于需要截枝和截枝后的答案更新。
这就是我自己新建一个class和对应的HashMap去记录进行截枝。
我的观念是这个样子的，在遇到重复出现过的节点单词的时候，首先考虑的是这个节点
往下遍历过后是否出现过解，如果没有的话只有两种情况：1，这个节点往下走是没有
解的。（在不变回去的情况下）2.变回去了。 这种情况下都当做无效访问往上一层走。
如果有的话，就比较该节点之前有解的情况下它所居的递归层数是否比当前重复访问的
时候深，如果否，则不更新，如果是，则根据层数差来修正结果。这相当于把之前遍历
过的结果默认放在这一层下面了。
好吧，问题来了。。这个解只能过leetcode 80%的cases。在一个字典很大的case中比
Expected answer多了1. 有没有人能告诉我听我的代码或者逻辑问题出在哪儿了？=。=
class DataSet{
int level, res;
DataSet(){
level = 0;
res = Integer.MAX_VALUE;
}
DataSet(int level){
this();
this.level = level;
}
}
public int ladderLength(String start, String end, Set dict) {
char[] start_arr = start.toCharArray();
Map marked = new HashMap();
int res = ladderlength(start_arr, end, dict, marked, 1);
return res == Integer.MAX_VALUE ? 0 : curmin;
}
int curmin = Integer.MAX_VALUE;
public int ladderlength(char[] start, String end, Set dict, Map<
String, DataSet> marked, int level){
String str = new String(start);
if(str.equals(end))
return level;
if(level > curmin)
return Integer.MAX_VALUE;
if(marked.containsKey(str)){
if(marked.get(str).res == Integer.MAX_VALUE)
return Integer.MAX_VALUE;
else{
if(marked.get(str).level < level)
return marked.get(str).res;
else{
marked.get(str).res = marked.get(str).res - (marked.get(
str).level - level);
marked.get(str).level = level;
return marked.get(str).res;
}
}
}
DataSet level_data = new DataSet(level);
marked.put(str, level_data);
int min = Integer.MAX_VALUE;
for(int i = 0; i < start.length; i++){
char tmp = start[i];
int minlevel = Integer.MAX_VALUE;
for(char j = 'a'; j <= 'z'; j++){
start[i] = j;
String tmpstr = new String(start);
if(dict.contains(tmpstr) && start[i] != tmp){
minlevel = Math.min(ladderlength(start, end, dict,
marked, level + 1), minlevel);
curmin = Math.min(curmin, minlevel);
}
}
start[i] = tmp;
min = Math.min(min, minlevel);
}
level_data.res = min;
return min;
} |
|
