辞書内の文字列の中で最も長いサブシーケンスを見つける

Question

"abccdde" のような文字列の中で最も長いサブシーケンスを見つけ、辞書{"ab"、 "add"、 "aced"} とする。上記の例の結果は

を「追加」されているIがインタビューで頼まれた、私は、トライ木を使用して答えを与え、最悪の場合はO（N×m個） であり、n S の長さであり、Mは長さ辞書の。 しかし、私の平均費用は非常に低くすべきです。面接官は、自分の解決策が最善のものではないと思ったので、私は面接に失敗します。誰か良いアイデアはありますか？

Answer 1

あなたはこの方法

public static Boolean IsSubsequence(string ch, string item) 
{ 
    if (ch.Length < item.Length) 
    { 
     return false; 
    } 
    int indexItem = 0; 
    int indexCh = 0; 
    while (indexCh < ch.Length && indexItem< item.Length) 
    { 
     if (ch[indexCh] == item[indexItem]) 
     { 
      indexItem++; 
     } 
     indexCh++; 
    } 
    return indexItem == item.Length; 
} 

を使用することができますこれであなたもtrueを返す最初のものは結果

Answer 2

になりますので単語な長さで辞書項目をソートすることによって開始することができ O（n）の方法グラフを作成すると、頂点はアルファベットになります。あなたは、各文字のためのあなたのテキストを訪問しているとき、あなたはその手紙のためのadyacencyリストをご覧ください。

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

：あなたの辞書内の各単語について、あなたは次のようにグラフの何かの最初の文字を追加します。リストの各項目について、その単語の次の文字を追加する必要があります。あなたの例では

：

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

まずステップ：Sの各文字

• 文字= '' のために

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

  - > S [0 ]

あなたは、その文字

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

とあなたのグラフを更新

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

• 文字 'B' のリストを訪問 - あなたが訪問する> S [1]

をその文字のリスト

[{"ab", 1}] 

、あなたは「AB」を終えたとして、あなたはあなたの答えを改善しようとすることができます

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

あなたのグラフを更新します。

• 文字 '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}]}} 

0を更新

...

Answer 3

この接頭辞を持つデフォルトの場合（一致する文字を追加して、（1つの文字長い言葉を見て）それぞれの有効な文字を使用すると、ツリーに深く進出するような辞書データ構造を配置）は、現在の深さよりも短い最長の有効なプレフィックスを指します（また、あなたの最良の選択肢であると判明した場合に備えて、すでに単語があることを示すフラグ）。あなたが「R」に続いて「asparag」に関するミスを取得すると

は、あなたの辞書にはそのような言葉がある場合に限っ「sparag」のツリーにあなたを指示し、そうでない場合、それはあなたを指示する「parag」 。

それぞれの失敗に対して、一致するものがない場合は、テストを繰り返し、短い単語に再帰します。だから、これはまだO（n）よりも悪いです...カジュアル思考の瞬間は、最悪の場合がO（2n）かもしれないことを示唆していますが。

これをスピードアップするには、リスト（現在の文字に一致するエントリを選択するデフォルト）を使用します。すべてのエントリは少なくとも長さ0（現在の文字は単語を開始しません）または1（現在の文字のみ）のエントリと一致します。

Answer 4

ここで、Nは文字列内の文字数（ "abccdde"の場合はN = 7）で、時間複雑度O（N + L）のソリューションのPythonコードです.Lは文字の合計数（ "ab"、 "add"、 "aced"の場合はL = 9）。基本的には、それは線形時間の複雑さです。

def find_longest_word_in_string(string, words): 
    m = {} 

    for word in words: 
     m[word] = 0 

    for c in string: 
     for word in m.keys(): 
      if len(word) == m[word]: 
       continue 
      else: 
       if word[m[word]] == c: 
        m[word] += 1 

    length = 0 
    for word in m.keys(): 
     if m[word] == len(word) and m[word] > length: 
      res = word 
      length = m[word] 

    return res 

if __name__ == '__main__': 
    s = "abccdde"     
    words = ["ab","add","aced"]  
    print find_longest_word_in_string(s, words) 

それは、リターン