string - 使用字典查找可能是原始字符串的所有可能单词的列表

Question

我的 friend 在他的一次采访中提出了这个问题。尽管他没有逐字记住这个问题，但他还是能尽其所能记忆起下面的内容。

一个字符串(一个单词)从发送方发送到接收方。在传输过程中，字符串中的一个字母被改变。使用字典查找可能是原始字符串的所有可能单词的列表。您不知道原始字符串是什么，您只能访问收到的字符串和字典。

第一次看到这个问题时，我想到的第一件事就是迭代替换字符串中的所有字符，然后将它们与字典中的单词进行比较。如果有匹配项，那么我会将那个词存储在一个数组中。(假设不区分大小写)

例如:

原词:猫

收到的字:bat

我的算法:

遍历字典，把OriginalWord.length()的所有单词放到一个HashTable中

[a-z]at .....检查这些是否在 hashTable 中

b[a-z]t....检查这些是否在哈希表中

ba[a-z]....检查这些是否在 hashTable 中

friend 说这是他用的算法，面试官说没有优化。我一直在研究这个问题，虽然我没有发现完全喜欢它。我发现了一些引用 Levenshtein 距离的内容。我对高级算法的了解有限，所以我无法理解它。另外，由于我无法访问面试官，所以我无法回答具体问题(例如，是否允许对字典进行预处理，在某某场景中会发生什么等等...)。尽可能地解释问题并做出合理的假设。

假设允许对字典进行预处理。在这种情况下问面试官什么问题比较好，什么是可以用来解决这个问题的更好/更优化的算法？

Answer 1

如果您允许通过创建 automaton 来预处理字典，则可以在线性时间内解决。 .

首先创建一个自动机来决定一个字符串是否在字典中。 Aho Corasick是创建这种自动机的算法的一个例子。 trie基本上也是在做同样的事情(尽管效率较低)

复制这个自动机，你现在有两个自动机，Q1，Q2。起始状态在 Q1 中，结束状态在 Q2 中。通过从 Q1 中的每个状态到 Q2 中的下一个状态添加一个非确定性步骤来连接自动机，但具有不同的特征。

例如，如果您有状态:

A---a-->B

添加:

A--b-->B'. A--c-->B', ...., A--z-->B'

其中 A、B 是 Q1 中的状态，B' 是等同于 B 的状态 - 但在 Q2 中。

这允许您通过转到 Q2 来忽略一个错误(然后您不能再忽略任何错误)。

自动机创建完成后(并处理回确定性自动机)，在查询时，您将在线性时间内获得匹配。