Design Add and Search Words Data Structure

Q: Wie hoch ist die Zeitkomplexität beim Hinzufügen und Suchen von Wörtern?

Das Hinzufügen eines Wortes der Länge L benötigt O(L) , ebenso wie eine Suche ohne Punkte, unabhängig davon, wie viele Wörter gespeichert sind. Eine Suche mit d Punkten benötigt im schlimmsten Fall O(26^d · L) . Der Speicherbedarf beträgt O(T) Knoten für T hinzugefügte Buchstaben.

MittelTrie Backtracking

+10

Erstelle ein Wörterbuch mit zwei Operationen. addWord w speichert das Wort w. search p gibt an, ob ein gespeichertes Wort zum Muster p passt: gleiche Länge, und an jeder Position steht im Muster derselbe Buchstabe oder ein Punkt ., der für einen beliebigen einzelnen Buchstaben steht.

Die Operation i ist ops[i] für das Wort oder Muster words[i]. Führe sie der Reihe nach mit einem leeren Wörterbuch aus und gib jeweils einen String zurück: "null" für ein addWord, "true" oder "false" für eine search.

Funktion

wordDictionaryOps(ops: string-array, words: string-array) → string-array

opsstring-array: die Operationen in der Reihenfolge, in der sie ausgeführt werden
wordsstring-array: das Wort, das hinzugefügt werden soll, oder das Muster, nach dem gesucht werden soll, jeweils eines pro Vorgang
Gibt zurückstring-array: eine Antwort pro Operation, als Text

Einschränkungen

1 ≤ ops.length ≤ 2500
words.length == ops.length
Jedes ops[i] ist addWord oder search.
1 ≤ words[i].length ≤ 20
Ein hinzuzufügendes Wort enthält nur englische Kleinbuchstaben.
Ein Suchmuster enthält englische Kleinbuchstaben und höchstens 3 Punkte.

Beispiele

Eingabe: ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Ausgabe: ["null", "null", "true", "false", "false", "true"]
Erklärung: r.se passt auf beide Wörter: Der Punkt steht für das o in rose und das i in rise. Ein Punkt steht niemals für einen fehlenden Buchstaben, daher passen ros und rose. nicht. ..s. passt, da bei beiden Wörtern das s an dritter Stelle steht.

Eingabe: ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
Ausgabe: ["false", "null", "true", "true", "false"]
Erklärung: Das Wörterbuch ist anfangs leer, daher findet ... nichts. Sobald sky hinzugefügt wurde, passen sowohl ... als auch s.y, während sk zu kurz ist.

Eingabe: ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
Ausgabe: ["null", "null", "true", "false", "true"]
Erklärung: Der erste Punkt in ma..o kann für das p von maple oder das n von mango stehen; maple endet auf e, aber mango passt. Kein Wort endet auf y, also schlägt m...y fehl, und m.p.e entspricht maple.

Weiterführende Frage

Wie würdest du search erweitern, wenn ein Muster auch * enthalten könnte, das für eine beliebige Folge von Buchstaben steht, auch für eine leere?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Punkt bedeutet, dass eine Suche das gesuchte Wort nicht benennen kann: ma..o steht für 676 mögliche Wörter, und nur die gespeicherten sind relevant. In einem Trie teilen sich Wörter mit gleichem Anfang einen Pfad. Ein Buchstabe im Muster folgt einem Link, ein Punkt verzweigt sich nur zu vorhandenen Kindern, und eine Tiefensuche kehrt von Sackgassen zurück.

Vergleiche das Muster mit jedem gespeicherten Wort

Idee

Behalte die hinzugefügten Wörter in einer Liste und prüfe jedes davon anhand des Musters: gleiche Länge und an jeder Position ein Punkt oder derselbe Buchstabe. Das ist die Definition einer Übereinstimmung. Da jedes gespeicherte Wort geprüft wird, ist die Antwort richtig.

Jede Suche muss die gesamte Liste durchgehen: O(n·L) für n Wörter mit bis zu L Buchstaben, selbst bei einem Muster ohne Punkt. 1,250 Hinzufügungen gefolgt von 1,250 Suchen prüfen 1,250 × 1,250 = 1,562,500 Wörter.

Algorithmus

Behalte die hinzugefügten Wörter in einer Liste. Für addWord w füge w hinzu und speichere "null".
Vergleiche bei search p p Zeichen für Zeichen mit jedem Wort gleicher Länge, wobei ein Punkt für jeden Buchstaben stehen kann.
Speichere beim ersten Treffer "true" oder "false", wenn es keinen Treffer gibt.

def matches(pattern, word):
    # Same length, and every position holds a dot or the same letter.
    if len(pattern) != len(word):
        return False
    for p, w in zip(pattern, word):
        if p != "." and p != w:
            return False
    return True


def wordDictionaryOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            stored.append(word)
            result.append("null")
        else:
            found = any(matches(word, s) for s in stored)
            result.append("true" if found else "false")
    return result

Trie mit einer Tiefensuche über Punkte

Idee

Füge die Wörter in einen Trie ein: rose und rise teilen sich den r-Knoten und verzweigen sich dann in o und i. Ein End-Flag markiert jeden Knoten, an dem ein gespeichertes Wort endet. Ein Buchstabenmuster entspricht einem Pfad durch den Trie. Ein Punkt kann für jeden Buchstaben stehen. Pro Punkt werden daher alle vorhandenen Kindknoten ausprobiert; sobald einer zu einem Treffer führt, wird true zurückgegeben.

Bei ma..o hat der Knoten für ma die Kindknoten p und n. Über p erreicht der zweite Punkt l, das keinen o-Kindknoten hat. Daher geht die Suche zurück und probiert n: g, dann o, wo mango endet.

Ein Treffer muss das gesamte Muster an einem markierten Knoten aufbrauchen, wodurch die Länge berücksichtigt wird: ros endet an einem nicht markierten Knoten, und bei rose. gibt es keine weiteren Verknüpfungen. Ein Punkt öffnet höchstens 26 Zweige. Daher werden bei d Punkten höchstens 26^d · L Knoten besucht, und ein Muster ohne Punkte kostet O(L).

Algorithmus

Jeder Knoten hat Verknüpfungen zu seinen Kindern und ein End-Flag, das anfangs ausgeschaltet ist.
Für addWord w: Gehe w vom Stamm aus entlang, erstelle fehlende Knoten und setze das End-Flag dort, wo der Durchlauf endet.
match(node, i): Wenn i die Länge des Musters ist, gib das End-Flag des Knotens zurück.
Wenn p[i] ein Buchstabe ist, gib false zurück, falls sein Kind fehlt, andernfalls match(child, i+1). Wenn es ein Punkt ist, gib true zurück, wenn match(child, i+1) für irgendein vorhandenes Kind erfolgreich ist, andernfalls false.
Erfasse match(root, 0) für jede Suche und "null" für jedes Hinzufügen.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, pattern):
        return self._match(self.root, pattern, 0)

    def _match(self, node, pattern, i):
        # Can the path below node spell pattern[i:] and end on a stored word?
        if i == len(pattern):
            return node.is_end
        ch = pattern[i]
        if ch == ".":
            # A dot stands for any letter: try each child until one works.
            for child in node.children.values():
                if self._match(child, pattern, i + 1):
                    return True
            return False
        child = node.children.get(ch)
        return child is not None and self._match(child, pattern, i + 1)


def wordDictionaryOps(ops, words):
    dictionary = WordDictionary()
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            dictionary.add_word(word)
            result.append("null")
        else:
            result.append("true" if dictionary.search(word) else "false")
    return result

Stolperfallen und Grenzfälle

Dem ersten Kind überlassen, über einen Punkt zu entscheiden. Bei ma..o schlägt der p-Zweig fehl und der n-Zweig ist erfolgreich. Code, der das Ergebnis des ersten Kindes zurückgibt, antwortet daher false, wenn er zuerst p ausprobiert. Antworte erst dann mit false, wenn alle Kinder fehlschlagen.
true antworten, wenn das Muster bei einem beliebigen Knoten zu Ende ist. Nach dem Hinzufügen von rose erreicht ros einen Knoten, aber dort endet kein Wort. Prüfe das End-Flag.
Einen Punkt ein fehlendes Zeichen abgleichen lassen. card. passt auf cards, aber nicht auf card.
Einen Punkt als Buchstaben behandeln. Bei der Indizierung eines Arrays mit 26 Plätzen mit '.' - 'a' wird außerhalb des Arrays gelesen; prüfe daher zuerst auf den Punkt.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität beim Hinzufügen und Suchen von Wörtern?

Das Hinzufügen eines Wortes der Länge L benötigt O(L), ebenso wie eine Suche ohne Punkte, unabhängig davon, wie viele Wörter gespeichert sind. Eine Suche mit d Punkten benötigt im schlimmsten Fall O(26^d · L). Der Speicherbedarf beträgt O(T) Knoten für T hinzugefügte Buchstaben.

Kannst du es mit einem Hash-Set statt einem Trie lösen?

Ja, allerdings mit Kompromissen. Ein Set beantwortet ein Muster ohne Punkte mit einem einzigen Nachschlagevorgang. Bei Punkten musst du entweder jedes gespeicherte Wort dieser Länge durchlaufen, O(n·L), oder jeden Punkt mit allen 26 Buchstaben füllen und jedes Ergebnis nachschlagen: 17.576 Nachschlagevorgänge bei drei Punkten.

Soll die Suche im Trie rekursiv oder iterativ sein?

Beides funktioniert. Die Rekursion geht pro Musterbuchstaben eine Ebene tiefer, hier höchstens 20, sodass der Aufrufstapel klein bleibt. Eine iterative Version hält einen Stapel aus (Knoten, Position)-Paaren vor und legt bei einem Punkt jedes Kind darauf.

def wordDictionaryOps(ops, words):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

ops = ["addWord", "addWord", "search", "search", "search", "search"]
words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]

Erwartete Ausgabe

["null", "null", "true", "false", "false", "true"]