为什么哈希集的性能比列表快得多？

Question

此问题来自leetcode(https://leetcode.com/problems/word-ladder/)！

给定两个单词(beginWord和endWord)，以及字典的单词列表，找到从beginWord到endWord的最短转换序列的长度，使得：

一次只能更改一个字母。每个转换后的单词都必须存在于单词列表中。请注意，beginWord不是一个经过转换的单词。注：

如果没有这样的转换序列，则返回0。所有单词的长度都相同。所有单词都只包含小写字母字符。你可以假设单词表中没有重复的单词。您可以假设beginWord和endWord不为空，并且不相同。

这是我的代码，运行需要800毫秒：

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList){
if(!wordList.contains(endWord))
return 0;
int ret = 1;
LinkedList<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<String>();
queue.offer(beginWord);
queue.offer(null);
while(queue.size() != 1 && !queue.isEmpty()) {
String temp = queue.poll();
if(temp == null){
ret++;
queue.offer(null);
continue;                
}
if(temp.equals(endWord)) {
//System.out.println("succ ret = " + ret);
return ret;
}
for(String word:wordList) {           
if(diffOf(temp,word) == 1){
//System.out.println("offered " + word);
//System.out.println("ret =" + ret);
if(!visited.contains(word)){
visited.add(word);
queue.offer(word); 
}
}
}
}
return 0;
}
private int diffOf(String s1, String s2) {
if(s1.length() != s2.length())
return Integer.MAX_VALUE;
int dif = 0;
for(int i=0;i < s1.length();i++) {
if(s1.charAt(i) != s2.charAt(i))
dif++;
}
return dif;    
}
}

这是另一个需要100毫秒才能运行的代码：

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) {
return 0;
}
int distance = 1;
Set<String> current = new HashSet<>();
current.add(beginWord);
while (!current.contains(endWord)) {
Set<String> next = new HashSet<>();
for (String str : current) {
for (int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String s = new String(chars);
if (s.equals(endWord)) {
return distance + 1;
}
if (set.contains(s)) {
next.add(s);
set.remove(s);
}
}
}
}
distance++;
if (next.size() == 0) {
return 0;
}
current = next;
}
return 0;
}
}

我认为第二个代码效率较低，因为它为每个单词测试26个字母。为什么这么快？

Answer 1

简短回答：你的呼吸优先搜索在每个"单词距离单位"(以下称为迭代)中进行的比较要多几个数量级。

• 你将每个候选词与剩下的每个词进行比较。每次迭代的时间复杂度T(N×
• 他们把每一个候选人都比作人工构建的"下一个"候选人。因为他们构建了候选者，所以他们不必"计算"距离。为了简单起见，我假设两者(构造或检查)具有相同的运行时间。每次迭代的时间复杂度为T(26×

(N=单词列表大小，N=此迭代的候选数量，l=单词长度)

当然，26×l×n远小于n×n，因为单词长度很小，但单词列表很大。

我在("and","has",[List of 2M English words])上试过你的程序，30秒后我把它杀死了，因为我认为它崩溃了。它没有坠毁，只是速度很慢。我转向另一个单词列表50K，而你的单词列表现在需要8秒，而它们的实现需要0.04秒。

我的单词表N=51306有2167个三字母单词。这意味着，平均每个单词都有3×cbrt(2167)个可能的候选者，即n≈38.82。

• 它们的预期性能：每次迭代T(26×
• 您的预期性能：每次迭代T(N×N)≈T(1991784)功

_{(假设单词列表不会变短；但有这么多单词，差异可以忽略不计)}

---

顺便说一句，基于队列的循环缓冲区实现可能比它们的两个交替集实现更快，因此您可以制作更快的混合。