-1

最近、あるインタビューでこんな質問を受けました。

辞書と開始文字列が与えられた場合、入力文字列の前後に 1 文字ずつ追加して形成できる最長の単語はどれですか?新しい単語もすべて辞書に含まれている必要があります。

例: input = 'at' Dict = {hat, chat, chats, rat, tat, tats, chatats}

「チャット」を返す理由: at -> hat -> chat -> chats

入力文字列の前後に a ～ z のすべての文字をブルートフォースで追加し、新しい文字列が存在する場合は、26 文字を前後にブルートフォースして最終的な文字列を取得するソリューションを考えました。

毎回26文字すべてを強制的に前後に強制することなく、この問題を解決するためのより効率的な方法があるかどうか疑問に思っていましたか?

私が考えた 1 つのアプローチは、辞書を調べて、入力文字列を変更する長さよりも 1 だけ長いエントリの部分文字列として入力文字列が存在する場合、エントリ文字列から入力部分文字列を削除することでした。

例: 1 回目の繰り返しの後、dict は = {h, chat, chats, r, t, tats, chatats} になります。

また、エントリの元の長さを追跡する各エントリの長さ変数も用意します。しかし、これが正しいアプローチであるかどうか、または機能するかどうかは正確にはわかりません。

4

1 に答える 1

1

単語とその短い/長いバージョンのグラフを作成します。たとえば、質問 ( hat, chat, chats, rat, tat, tats, chatats) の単語リストについては、次のようになります。

                           chatats
hat ─── chat ─── chats
rat
tat ─── tats

グラフを逆方向に作成します。つまり、単語ごとに、先頭または末尾の文字を削除して 2 つの短い単語を探します。

検索を高速化するにはMap、単語をグラフ ノードに作成します。

グラフで最長のチェーンを見つけます。

于 2017-09-26T08:24:51.207 に答える