4

これはインタビューの質問です。いくつかの文字列が与えられた場合、他の文字列の接頭辞であるそのような文字列を見つけます。たとえばstrings = {"a", "aa", "ab", abb"}、結果が であるとし{"a", "ab"}ます。

最も簡単な解決策は、文字列を並べ替えて、最初の文字列が 2 番目の文字列のプレフィックスであるかどうかを確認することです。アルゴリズムの実行時間は、並べ替えの実行時間です。

trieを使用し、複雑さを持つ別のソリューションがあると思いO(N)ます。ここで、N は文字列の数です。そのようなアルゴリズムを提案できますか?

4

2 に答える 2

6

Trie、複雑さO（N）に関して次の考えがあります。空のTrieから始めます。単語を1つずつ取り、Trieに単語を追加します。Trieに単語（単語Wiと呼びましょう）を追加した後、考慮すべき2つのケースがあります。

  1. Wiは、前に追加したいくつかの単語の接頭辞です。Wiという単語を追加しているときに、Trieにノードを追加しなかった場合、このステートメントは当てはまります。その場合、Wiはプレフィックスであり、ソリューションの一部です。
  2. 前に追加された単語のいくつかはWiの接頭辞です。そのステートメントは、前に追加された単語の終わりを表すノードを通過した場合に当てはまります（その単語Wjを計算しましょう）。その場合、WjはWiのプレフィックスであり、ソリューションの一部です。

詳細（擬似コード）：

for word in words
    add word to trie
    if size of trie did not change then   // first case
        add word to result
    if ending nodes found while adding word   // second case
        add words defined by those nodes to result
return result

Trieに新しい単語を追加する：

node = trie.root();
for letter in word
    if node.hasChild(letter) == false then   // if letter doesnt exist, add it
        node.addChild(letter)
    if letter is last_letter_of_word then   // if last letter of word, store that info
        node.setIsLastLetterOf(word)
    node = node.getChild(letter)    // move

新しい単語を追加しているときに、他の単語の最後の文字を表すノードを通過したかどうかを確認することもできます。私が説明したアルゴリズムの複雑さはO（N）です。もう1つの重要なことは、この方法で、単語Wiが他の単語に接頭辞を付ける回数を知ることができることです。これは便利な場合があります。

{aab、aaba、aa}の例：緑のノードはケース1として検出されたノードです。赤のノードはケース2として検出されたノードです。各列（試行）は1つのステップです。最初はトライは空です。黒い矢印は、そのステップでアクセス（追加）したノードを示しています。ある単語の最後の文字を表すノードでは、その単語が括弧で囲まれています。

ここに画像の説明を入力してください

  1. ステップ1では、単語aabを追加します。
  2. ステップ2では、単語aabaを追加し、1つのケース2（単語aab）を認識して、結果に単語aabを追加します。
  3. ステップ3では、単語aaを追加し、ケース1を認識して、結果に単語aaを追加します。

最後に、正しい結果= {aab、aa}が得られます。

于 2012-07-09T14:40:45.177 に答える
3

元の答えは次の場合に正しいです: is a string aa substring of b(misread)。

トライを使用すると、最初の反復ですべての文字列を単純に追加し、2 回目の反復で各単語の読み取りを開始できますw。読み終わったが、文字列ターミネータに達していない単語を見つけた場合 ($通常)、vトライのいくつかのノードに到達します。 からDFS
を実行すると、それらのプレフィックスであるすべての文字列を取得できます。vw

高レベルの擬似コード:

t <- new trie
for each word w:
   t.add(w)
for each word w:
  node <- t.getLastNode(w)
  if node.val != $
     collection<- DFS(node) (excluding w itself)
     w is a prefix of each word in collection

注: 最適化するために、追加の作業が必要になる場合があります: ifaが の接頭辞でありb、bが の接頭辞である場合c、aは の接頭辞cです。つまり、DFS を実行するときに、すでに検索されたノードに到達した場合は、その文字列を現在のプレフィックスに追加するだけです。
それでも、2 次数の可能性 ( "a", "aa", "aaa", ....) が存在する可能性があるため、それらすべてを取得するには 2 次時間が必要です。

元の答え:aが の部分文字列かどうかを調べるb:

提案された解は 2 次複雑度で実行されます。2 つのペアをそれぞれチェックする必要がありますO(n* (n-1) * |S|)。

最初の繰り返しで文字列からサフィックス ツリーを構築し、2 回目の繰り返しで、各文字列が別の文字列の重要なエントリ (それ自体ではない) であるかどうかを確認できます。
この解決策はO(n*|S|)

于 2012-07-09T14:33:15.397 に答える