Finde die kleinsten Subset-Präfixe

Question

Hier ist mein Code für dieses Problem. Ich benutze Trie Baum für diese Lösung und frage mich, ob andere bessere Ideen in Bezug auf bessere Zeit Komplexität oder Komplexität des Raumes. Auch Bugs und Codestil-Ratschläge sind willkommen.

Problem:

eine Menge von Strings gegeben, kehrt die kleinste Teilmenge des gegebenen Eingangswortes gesetzt --- eingestellten Präfixe für alle Eingangsworte im gegebenen Eingangswort enthält. Das Präfix sollte ein vollständiges Eingabewort in dem gegebenen Eingabesatz sein, mit Ausnahme eines Präfixes eines gegebenen Wortes. Für ein Wort, das kein Präfix hat, gibt sich selbst zurück.

Wenn die Liste [ 'foo', 'FOOG', 'Lebensmittel', 'asdf'] return [ 'foo', 'asdf']

Die Rückkehr ist foo seit foo ist Präfix für foo (selbst), Präfix für foog und Präfix für food (mit anderen Worten, foo könnte längere Zeichenfolge wie foog und food "darstellen"). Ausgabe enthält auch asdf, weil es kein Präfix für andere Wörter in der Eingabeliste ist, also selbst ausgegeben.

Der leere Satz ist keine richtige Antwort, da er nicht die längsten möglichen Präfixe enthält.

Quellcode:

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

Ich denke, die Frage eindeutig ist. (Vielleicht war es vor den Änderungen härter). Die Antwort ist, dass Trie genau richtig erscheint.

Erstellen Sie einen Trie aus den Eingabewörtern, dann durchlaufen Sie zuerst die Tiefe. Jedes Mal, wenn Sie einen Knoten (einen inneren Knoten oder ein Blatt) finden, der sich im Eingabe-Set befindet, fügen Sie das Wort an diesem Knoten zur Ausgabe hinzu und hören auf, die untergeordneten Elemente zu durchsuchen.

Answer 2

Ich ziehe den einfacheren while -loop Ansatz mit einer Art am Anfang:

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 

Es ist eine ziemlich effiziente Umsetzung im schlimmsten Fall O läuft in (n ** 2), wenn kein String ist ein Präfix jede andere Zeichenfolge.

---

Postscript # 1: Sie können die Art etwas effizienter machen, indem nur von der Länge der Wörter Sortierung anstelle von Länge und alphabetisch. B. diese Zeile ändert:

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

zu:

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

natürlich eine Art ist O (n (log n)), welche die untere gebunden ist auf der Laufzeit/Komplexität.

---

Postscript # 2:

Wenn Sie Speichereigenschaften definiert bevorzugen, können Sie anstelle der Filterung auf der words Liste Markierung verwenden.Eine Markierung Version dieses Algorithmus würde wie folgt aussehen:

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 ] 

etwas ausführlicher als meine bevorzugte Filterversion ist, hat aber den Vorteil, nicht ständig die Schaffung/in jedem aufeinanderfolgenden Durchlauf der Schleife die Worte Array zu zerstören.