algorithm - 辞書で文字列の最長の部分列を見つける

Question

"abccdde" などの String の最長部分列を検索し、辞書 {"ab","add","aced"} を指定します。上記の例の結果は「追加」です

インタビューで聞かれたので、トライ木を使って答えました。最悪のケースは O(n*m) で、n は s の長さ、m は辞書の長さです。しかし、私の平均コストは非常に低いはずです。面接担当者が私の解決策が最善ではないと考えたため、面接に失敗しました。誰かがより良いアイデアを持っていますか?

Answer 1

グラフを作成すると、頂点がアルファベットになります。辞書の単語ごとに、グラフの最初の文字を次のように追加します。

G[word[0]].add({word, 0})

次に、各文字のテキストにアクセスしているときに、その文字の adyacency リストにアクセスします。リスト内の各項目について、その単語の次の文字を追加する必要があります。

あなたの例では：

S = "abccdde", D = {"ab","add","aced"}

最初の一歩：

G = {{'a', [{"ab", 0}, {"add", 0}, {"aced", 0}]}}

Sの各キャラクターについて

• 文字 = 'a' -> S[0]

そのキャラクターのリストにアクセスします

[{"ab", 0}, {"add", 0}, {"aced", 0}]

グラフを更新します

G = {{'b', [{"ab", 1}]}, {'d', ["add", 1]}, {'c', [{"aced", 1}]}}

• 文字 'b' -> S[1]

そのキャラクターのリストにアクセスします

[{"ab", 1}]

グラフを更新します

G = {{'d', ["add", 1]}, {'c', [{"aced", 1}]}}

「ab」を終えたら、答えを改善することができます。

• 文字 'c' -> S[2]

そのキャラクターのリストにアクセスします

[{"aced", 1}]

グラフを更新します

G = {{'d', ["add", 1]}, {'e', [{"aced", 2}]}}

• 文字 'c' -> S[3]

その文字のリストがない場合は、次の文字に進みます

• 文字 'd' -> S[4]

そのキャラクターのリストにアクセスします

["add", 1]

グラフを更新します

G = {{'d', ["add", 2]}, {'e', [{"aced", 2}]}}

...