最小サブセットプレフィックスを見つける

Question

これは私のこの問題のコードです。私はこのソリューションのためにTrie treeを使用しています。時間の複雑さや空間の複雑さの点で他の優れたアイデアがあるかどうかは疑問です。また、バグやコードスタイルに関するアドバイスも感謝しています。

問題：文字列の集合が与えられる

、与えられた入力ワードセット内のすべての入力単語の接頭辞が含まれて設定された所定の入力ワードの最小サブセットを---返します。プレフィックスは、指定された入力セット内の完全な入力単語でなければなりません。プレフィックスを持たない単語の場合は、 がそれ自身を返します。

リストがある場合は[ 'FOO'、 'foog'、 '食べ物'、 '空自']リターン[ 'FOO'、 '空自']

リターンはfoo以来fooあるの接頭辞でありますfoo（それ自体）、foogの接頭辞、foodの接頭辞（つまり、fooは、foogとfoodのような長い文字列を表すことができます）。入力リストの他の単語の接頭辞ではないため、出力にはasdfも含まれているため、出力自体が出力されます。

空のセットは、可能な限り長いプレフィックスが含まれていないため、正解ではありません。

ソースコード：

from collections import defaultdict 
class TrieNode: 
    def __init__(self): 
     self.children = defaultdict(TrieNode) 
     self.isEnd = False 
    def insert(self, word): 
     node = self 
     for w in word: 
      node = node.children[w] 
     node.isEnd = True 
    def find_prefix(self, prefix, result): 
     if self.isEnd: 
      result.append(prefix[:]) 
      return 
     for k,v in self.children.items(): 
      prefix.append(k) 
      v.find_prefix(prefix, result) 
      prefix.pop(-1) 

if __name__ == "__main__": 
    words = ['foo', 'foog', 'food', 'asdf'] 
    root = TrieNode() 
    for w in words: 
     root.insert(w) 
    result = [] 
    root.find_prefix([], result) 
    print result 

Answer 1

私は質問があいまいだと思います。 （たぶんそれは編集の前に厳しいものでした）。答えは、トライが正確に正しいと思われることです。

入力語からトライを作成してから、最初にトラバースします。入力セット内にあるノード（内部ノードまたはリーフ）を見つけるたびに、そのノードの単語を出力に追加し、その子の検索をやめます。

Answer 2

私が先頭にソートして単純while -loopアプローチを好む：

minimal = [] 
words = ['foo', 'foog', 'food', 'asdf'] 
words.sort(key=lambda x: (len(x), x)) 
while words: 
    word = words[0] 
    minimal.append(word) 
    words = [ x for x in words[1:] if not x.startswith(word) ] 
print minimal 

それは最悪Oでで実行されている非常に効率的な実装である（N ** 2）は、文字列は接頭辞のないとき他の文字列。

---

ポストスクリプト＃1：あなたは少しより効率的なだけの代わりに、両方の長さの単語の長さにソートすることにより、およびアルファベット順に並べ替えを行うことができます。例えば、この行を変更：

words.sort(key=lambda x: (len(x), x)) 

に：もちろん

words.sort(key=lambda x: len(x)) 

ソートすることであるO（N（ログn））走行時間/複雑さの下限です。

---

ポストスクリプト＃2：

あなたが定義したメモリ特性を好む場合は、マーキングの代わりwordsリストにフィルタリングを使用することができます。このアルゴリズムのマーキングバージョンは、次のようになります。それは少し冗長な私の好みのフィルタリングバージョンよりもですが、継続的に作成/ループの各連続パス内の単語の配列を破壊しないという利点があり

words = [ 'foo', 'foog', 'food', 'asdf' ] 
    words.sort(key=lambda x: len(x)) 
    marked = [ False for _ in words ] 
    for i in range(0, len(words)): 
     is_marked = marked[i] 
     if is_marked: continue 
     word = words[i] 

     for j in range(i + 1, len(words)): 
      if not marked[j] and words[j].startswith(word): 
       marked[j] = True 
    minimal = [ word for word, is_marked in zip(words, marked) if not is_marked ] 

。