leetcode 127号问题
来源:7-2 图论建模的核心:状态表达
讲武德的年轻人
2022-04-12
bobo老师,我用bfs思路做了lc 127 word ladder题目(https://leetcode.com/problems/word-ladder/)。用了和您github中类似的方法通过了。后来,我又优化了寻找当前单词cur的相邻单词的函数(代码如下),但是只有总共50个case中,只有33个case能够通过,出现了超时错误。我检查了很久还是没有发现问题,能否请您看下?谢谢!
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord))
return 0;
// bfs
Queue<String> queue = new ArrayDeque<>();
queue.offer(beginWord);
Map<String, Integer> map = new HashMap<>();
map.put(beginWord, 1);
while (!queue.isEmpty()) {
String cur = queue.poll();
//遍历cur的所有“相邻”单词
for (String str : getNextWords(cur, wordList) ) {
if (!map.containsKey(str)) {
queue.offer(str);
map.put(str, map.get(cur) + 1);
if (str.equals(endWord))
return map.get(str);
}
}
}
return 0;
}
// 替换单词str在位置i的字符为c
private String replace(String str, int i, char c) {
char[] chrs = str.toCharArray();
chrs[i] = c;
return new String(chrs);
}
// 生成单词cur的相邻节点的集合:字符只有一个不相同的所有单词
// 思路:依次改变cur的每个位置的字符: 从a到z。如果改变一次后在wordList中,则收集到集合中作为相邻节点。
private ArrayList<String> getNextWords(String cur, List<String> wordList) {
ArrayList<String> adj = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c ++) {
for (int i = 0; i < cur.length(); i ++) {
if (cur.charAt(i) == c)
continue;
String newWord = replace(cur, i, c);
if (wordList.contains(newWord)) {
adj.add(newWord);
}
}
}
return adj;
}
}写回答
1回答
-
liuyubobobo
2022-04-13
超时说明没有逻辑问题,是性能可以优化。
我不确定你说的“类似的方法通过了”是什么方法,但我的 github 代码仓中的两个方法都比你现在的方式有性能优化。
这一版代码预处理了单词之间的转移关系,使得不需要在 bfs 的过程中不断生成和当前单词相邻的单词再不断判断是否遍历过(变量 g 的构建):https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0127-Word-Ladder/java-0127/src/Solution.java
这一版代码在不断缩小可以选取的 word 的集合(47-48 行):https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0127-Word-Ladder/java-0127/src/Solution2.java
剩下的两版代码使用了双向 bfs,这种方法通常面试不会考察。
继续加油!:)
00
相似问题