algorithm - 拼写检查重复字母

Question

我正在写一个拼写检查器。我对 Levenshtein 距离、尝试等都了如指掌……

然而，我的问题是，用重复的字母纠正一个单词，例如：haaaaapppppyyy to happy。解决这个问题的最佳方法是什么？

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

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

有什么建议么？

Answer 1

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