几天来,我一直在尝试思考一个简单的案例,当我对单词梯子问题的解决方案失败时。我尝试用内存来实现DP解决方案。我非常感谢您解释为什么 DP 在这里不起作用。以下是我实现(错误的)DP 解决方案的方法。
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int[] visited = new int[wordList.size()];
HashMap<String, Integer> map = new HashMap<>();
int res = ladderHelper( beginWord,endWord, wordList,visited,map);
return res;
}
private int ladderHelper(String beginWord, String endWord, List<String> wordList, int[] visited, HashMap<String, Integer> map) {
if (beginWord.equals(endWord)) return 1;
int bestSeen = 0;
for (int i = 0; i < wordList.size(); i++) {
if (visited[i] == 1) continue;
if (!validJump(beginWord, wordList.get(i))) continue;
if (map.containsKey(wordList.get(i))) {
int val = map.get(wordList.get(i));
if (val != 0 && val+ 1 < bestSeen) bestSeen = map.get(wordList.get(i))+1;
}else {
visited[i] = 1;
int distance = ladderHelper(wordList.get(i), endWord, wordList, visited, map);
visited[i] = 0;
if (distance != 0 && (bestSeen == 0 || distance + 1 < bestSeen)) bestSeen = distance+1;
}
}
map.put(beginWord, bestSeen);
return bestSeen;
}
private boolean validJump(String a, String b) {
int mistakes = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i) && ++mistakes > 1) return false;
}
return true;
}
}
问题给出更详细here .
最佳答案
我认为这段代码有一个琐碎而又有趣的问题。
小错误
行中:
if (val != 0 && val+ 1 < bestSeen) bestSeen = map.get(wordList.get(i))+1;
如果 bestSeen 等于 0(如果到目前为止所有值都已在缓存中,则出现这种情况),则此条件永远不会激活。您需要更多类似的东西:
if (val != 0 && (bestSeen==0 || val+ 1 < bestSeen)) bestSeen = map.get(wordList.get(i))+1;
这样做的效果是有时会忽略较短的路线。
有趣的错误
您正在使用 DFS 来尝试找到最短路径。如果您改用 BFS,我希望您的解决方案能够通过。
DFS失败的原因是由于访问的数组。 Visited 数组用于跟踪当前路径上的单词,以防止无限递归。问题是我们忽略了经过这些访问节点的所有路径。
乍一看这似乎很好,毕竟我们的最短路径永远不需要自行循环!
假设您的 DFS 代码访问了 A、B、C、D。
当它访问 D 时,它会查看其邻居,发现它们都被访问过,并得出结论,不可能存在从 D 到终点的路线!
当算法回溯时,最终会尝试路线start->D,但缓存会报告这条路线不可能,因此不会找到最短路径。
关于algorithm - 为什么字梯的动态编程解决方案不起作用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44579960/