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
相似问题
leetcode 1584号问题
回答 1
用C语言实现leetcode785号问题
回答 1
leetcode问题
回答 1
关于一题leetcode问题
回答 1
leetcode 1263问题
回答 1