为什么从 HashSet 中删除元素的代码比添加到 HashMap 需要更长的时间?

Question

我正在Leetcode上解决这个问题。 https://leetcode.com/problems/word-ladder

给定两个单词(beginWord和endWord(和一个字典的单词列表， 查找从 beginWord 到 endWord，这样：

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

我采用的方法需要 1100 毫秒的时间，编辑方法需要 43 毫秒的时间。尽管区别仅在于编辑使用哈希图而不是我使用的哈希集以及我的方法中额外的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- 但在将元素添加到队列后，也要从集合中删除该元素。