为什么从HashSet中删除元素的代码要比添加到HashMap中的时间长很多？

Question

我在Leetcode上解决这个问题。https:/leetcode.comproblemsword-ladder）。

给定两个单词(beginWord和endWord)，以及一个字典的单词表，找出从beginWord到endWord的最短转换序列的长度，这样。

1. 每次只能改变一个字母。
2. 每个转换后的单词必须存在于单词列表中。

我采取的方法需要1100毫秒的时间，编辑的方法需要43毫秒的时间。虽然两者的区别仅仅是编辑使用的是hashmap而不是我使用的hashset，并且在我的方法中多了一个hashset.remove()方法。由于时间差有点大，谁能帮我了解一下原因。谢谢。

下面是小编和我的解决方案这两段代码抢。它们几乎完全相同，不同之处在代码中明确标注。

我的解决方案：需要1100毫秒

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Map<String, ArrayList<String>> m = new HashMap<>();
        int len = beginWord.length();
        for(String word : wordList) {
            for(int i = 0; i < len; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i+1, len);
                m.computeIfAbsent(newWord, k -> new ArrayList<String>()).add(word);
            }
        }
        HashSet<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord))
            return 0;
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        int res = Integer.MAX_VALUE;;
        while(!q.isEmpty()) {

            int size = q.size();

            while(size-- > 0) {
                String s = q.poll();

                for(int i = 0; i < len; i++) {
                    String newWord = s.substring(0, i) + "*" + s.substring(i+1, len);
                    for(String str : m.getOrDefault(newWord, new ArrayList<>())) {
                        if(str.equals(endWord)) {
                            return level + 1;
                        }
                        *** The condition and content are different ***
                        if(set.contains(str))
                        q.offer(str);
                    }
                }
                set.remove(s);
            }
            level++;
        }

        return 0;
    }
}

编辑解决方案：需要40毫秒

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Map<String, ArrayList<String>> m = new HashMap<>();
        int len = beginWord.length();
        for(String word : wordList) {
            for(int i = 0; i < len; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i+1, len);
                m.computeIfAbsent(newWord, k -> new ArrayList<String>()).add(word);
            }
        }

        // Visited to make sure we don't repeat processing same word.
        ***Next line is not in my code***            
        Map<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);
        HashSet<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord))
            return 0;
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        int res = Integer.MAX_VALUE;;
        while(!q.isEmpty()) {

            int size = q.size();

            while(size-- > 0) {
                String s = q.poll();

                for(int i = 0; i < len; i++) {
                    String newWord = s.substring(0, i) + "*" + s.substring(i+1, len);
                    for(String str : m.getOrDefault(newWord, new ArrayList<>())) {
                        if(str.equals(endWord)) {
                            return level + 1;
                        }
                        *** The condition and content are different ***
                        if (!visited.containsKey(str)) {
                            visited.put(str, true);
                            q.add(str);
                        }
                    }
                }
            }
            level++;
        }

        return 0;
    }
}

Answer 1

这个问题基本上是在一个未加权的图中找一条最短路径，两种解法都使用了 BFS.

小编没有深入了解太多细节的解决方案，但你的解决方案并没有运行在 O(|V| + |E|)，因此可能是次优的。

请注意，您从 set 当你处理完它时，但你使用集来确定处理时，你的 增加 一个词到队列中。

想想这个例子。

dictionary = { aaa, aba, aab, abb, bbb }
start = aaa
end = bbb

first iteration:
set = { aaa, aba, aab, abb, bbb }
q = { aaa }
In this iteration: remove aaa from set and q, insert aba and aab.

second iteration:
set = { aba, aab, abb, bbb }
q = { aba, aab }
process aba:
add to queue abb
remove from set and q aba 
process aab: 
add to queue abb
remove from set and queue aab

third iteration:
set = { abb, bbb }
q = { abb, abb }
in this iteraiotn you will process abb twice, and add bbb twice.

这种行为会以指数形式增长, 每一个被插入两次的节点都可能会多次增加相同的节点, 导致2*2*2*... ...

解决方法很简单，你需要保持一致，在两个选项中选择一个。

1. 继续删除项目 set 原地踏步，却早早地加了一个 continue 从队列中轮询一个不在集合中的元素。
2. 继续检查一个元素是否在 set 在插入之前，也可以在将元素添加到队列中后将其从集合中移除。