辞書の単語の一般的なトライが構築されていると仮定すると、スペルミスの4つのケース(トラバーサル中の置換、削除、転置、挿入)をチェックするための最良の方法は何でしょうか?
1つの方法は、特定の単語のn個の編集距離内にあるすべての単語を把握し、Trieでそれらをチェックすることです。これは悪いオプションではありませんが、ここでのより良い直感は、トラバーサル中に単語を変更した後、動的計画法(または再帰的な同等の方法)を使用して最適なサブトライを決定することです。
どんなアイデアでも大歓迎です!
PS、回答のリンクだけでなく、実際の入力をいただければ幸いです。