c++ - 間にスペースを追加することによって意味のある単語を形成する単語が与えられた

Question

スペースのない文字列の例「Iamastudent」が表示されます。特定の単語が辞書に存在するかどうかを検証する定義済みの辞書機能が提供されます。この関数を使用すると、文字列にスペースを挿入して、「私は学生です」と出力する必要があります。

それは私のインタビューの質問で、C ++で解決しすぎると言われました。私は動的プログラミングを使用して解決しましたが、彼は私が与えた解決策が以下の質問と同じであることに満足していませんでした

スペースのないフレーズが与えられた場合、スペースを追加して適切な文を作成します

彼はトライまたはサフィックス配列を使用してそれを行うように私に頼みましたが、私は解決策を理解できませんでした。

Answer 1

文を分割する独自の解決策がある場合、トライでそれを行うのは簡単です:

1. 入力文字列に文字がある場合、文字列の文字を消費するルートから下に向かって歩き始めます。それ以外の場合は終了します。
2. それが圧縮されたトライの場合、プレフィックスが完全な単語であるときはいつでもマークが見つかります。それ以外の場合は、スペースを出力する葉に到達した場合です
3. 文字列の現在の位置から 1 に戻ります (ルートから下ります)。

文字列に文字がなくなったら完了です (この時点でツリーをトラバースしていないことを確認することをお勧めします)。

解が一意でない場合は、文字列の末尾に到達し、ツリーのマークまたはリーフに到達していないときはいつでも、以前に出力したスペースに戻る必要があります。入力文字列内の位置のスタックが必要です。