string - 从给定单词列表中查找是否有一个拼写错误的单词的最佳方法

Question

你会如何有效地解决这个问题

假设我们得到了一个单词列表 [“apple”、“banana”、“mango”]

如果我们在列表中得到一个错别字的单词， “苹果” “阿普尔” “申请” 我们输出 true

如果有多个错字，我们输出 false。

为了优化，我尝试将列表存储在包含每个单词的字母数的哈希表中，并在给定的输入中寻找相同数量的字母，以减少我们在其中查找输入的大小。我们可以对这个问题进行更快的优化吗？

Answer 1

一种可能的优化是为给定列表生成所有错别字并将它们放入映射(或一些更好的字符串查找结构)中。然后查找给定的单词 - 如果找到输出 true，否则输出 false。一个错别字的总数是:25*L，其中L是输入列表中的字母总数(假设不​​区分大小写)。