算法 - 检查给定单词是否存在单一类型

OHHH 发表于 Dev

呵呵

给定一个字典列表和一个输入单词，如果输入单词有一个与字典中的词汇长度相同的拼写错误，则返回 true。

dictionary = ["apple", "testing", "computer"];
singleType(dictionary, "adple") // true
singleType(dictionary, "addle") // false
singleType(dictionary, "apple") // false
singleType(dictionary, "apples") // false

如果我们忽略哈希图所需的预处理时间，我提出了一个以线性时间运行的解决方案。

O(k*26) => O(k)，在哪里 k = length of the input word

我的线性解决方案是，将字典列表转换为哈希映射，其中键是单词，值是布尔值，然后遍历输入单词中的每个字符，并用 26 个字母表中的 1 个替换每个字符，然后检查它是否映射到哈希映射。

但是他们说我可以做得比更好O(k*26)，但是如何呢？

tobias_k

你可以扩展所有的字典包含一个错字字的变体，但不是实际的错字，你只要把一些“通配符”像?或者*在那个地方。然后，您可以检查（a）该单词是否不在拼写正确的单词集中，以及（b）用相同的通配符替换单词中的任何字母，该单词可以在具有一个错字。

Python 中的示例：

>>> dictionary = ["apple", "testing", "computer"]
>>> wildcard = lambda w: [w[:i]+"?"+w[i+1:] for i in range(len(w))]
>>> onetypo = {x for w in dictionary for x in wildcard(w)}
>>> correct = {w for w in dictionary}
>>> word = "apxle"
>>> word not in correct and any(w in onetypo for w in wildcard(word))
True

这将查找的复杂性降低到 O(k)，即在字母数量方面仍然是线性的，但没有高常数因子。然而，它确实以一个等于单词中平均字母数的系数大大地炸毁了字典。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。