algorithm - 拼写检查重复字母

Question

我正在写一个拼写检查器。我知道所有关于 Levenshtein 距离、尝试等...

然而，我的问题是，要更正带有重复字母的单词，例如:haaaaapppppyyy 到 happy。解决这个问题的最佳方法是什么？

到目前为止，我正在考虑使用修改后的 trie，当我到达“a”并看到 trie 中没有另一个跟随“a”时，我跳过字符串中的所有 a，直到我到达 p 并从那里。

我不完全确定这是实现它的最佳方式，或者它是否适用于所有字符串。

有什么建议吗？

Answer 1

您可以创建一个新的 trie 并删除所有重复的字母(例如 happy -> hapy)。检查单词时，做同样的事情(haaaaapppppyyy -> hapy)并在 trie 中搜索它。