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,这种方法通常面试不会考察。


继续加油!:)

0
0

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程