技术实现：判断输入单词与字典单词是否存在单一同长度拼写错误

刚好之前也遇到过类似的需求，你的思路完全正确——我们确实可以用**O(k)**的线性时间复杂度（k为输入单词长度）来解决这个问题，核心就是哈希表的快速查找+枚举字符替换的思路。下面我把这个方案的细节拆解清楚，再附上代码示例：

整体思路 #

先把字典预处理成哈希集合（利用O(1)的查找效率），然后通过枚举输入单词每个位置的所有可能字符替换，快速验证是否存在符合"仅一处拼写错误"的字典单词。

具体步骤 #

• 预处理字典：
  首先把字典里所有和输入单词长度相同的单词提取出来，存入哈希集合（比如Python的set）。这一步的预处理时间我们可以忽略，重点看查询阶段的效率。
• 枚举每个字符位置的替换可能：
  遍历输入单词的每一个字符位置：
  1. 把当前位置的字符暂时"挖空"，保留前后部分的字符串（比如输入是"hello"，处理第2位时，前后部分就是"he"和"lo"）；
  2. 遍历26个英文字母，把"挖空"的位置替换成当前字母，生成候选单词；
  3. 如果候选单词存在于哈希集合中，并且不是输入单词本身（避免原单词就在字典里的情况，因为此时错误数为0，不符合要求），直接返回true；
• 最终结果：
  如果所有位置都遍历完，没找到符合条件的候选单词，就返回false。

代码示例（Python） #

def has_single_mistake_match(input_word, dictionary):
    # 只保留和输入单词长度一致的字典单词，存入集合
    valid_words = {word for word in dictionary if len(word) == len(input_word)}
    if not valid_words:
        return False
    
    word_length = len(input_word)
    for idx in range(word_length):
        # 拆分出当前位置的前后字符串
        prefix = input_word[:idx]
        suffix = input_word[idx+1:]
        
        # 遍历所有可能的英文字母
        for char in 'abcdefghijklmnopqrstuvwxyz':
            # 跳过原字符，避免匹配到输入单词本身
            if char == input_word[idx]:
                continue
            candidate = prefix + char + suffix
            if candidate in valid_words:
                return True
    return False

复杂度说明 #

正如你提到的，查询阶段的时间复杂度是O(k*26)，也就是O(k)的线性时间——因为26是常数，不影响复杂度的量级。哈希表的预处理时间是O(N*L)（N是字典单词数，L是平均单词长度），但通常这一步可以提前完成，或者相对于查询次数来说可以忽略。

内容的提问来源于stack exchange，提问作者Ohhh