Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

原题链接🔗：Implementieren Sie Trie (Präfixbaum)
Schwierigkeit: Mittel⭐️⭐️

Thema

Trie (ausgesprochen wie „try“) oder Präfixbaum Ist eine Baumdatenstruktur, die zum effizienten Speichern und Abrufen von Schlüsseln in einem Zeichenfolgendatensatz verwendet wird. Für diese Datenstruktur gibt es zahlreiche Anwendungsfälle, beispielsweise die automatische Vervollständigung und die Rechtschreibprüfung.

Bitte implementieren Sie die Trie-Klasse:

• Trie() Initialisieren Sie das Präfixbaumobjekt.
• void insert(String word) Fügen Sie eine Zeichenfolge in den Präfixbaum einword 。
• boolean search(String word) wenn Zeichenfolgeword Im Präfixbaum zurückkehren true(d. h. wurde vor dem Abruf eingefügt); andernfalls wird zurückgegeben false 。
• boolean startsWith(String prefix) Wenn die Zeichenfolge bereits zuvor eingefügt wurde wordEines der Präfixe ist prefix ,zurückkehren true ; Ansonsten zurückfalse。

Beispiel:

eingeben
[„Trie“, „einfügen“, „suchen“, „suchen“, „startsWith“, „einfügen“, „suchen“]
[[], [„Apfel“], [„Apfel“], [„App“], [„App“], [„App“], [„App“]]
Ausgabe
[null, null, wahr, falsch, wahr, null, wahr]

erklären
Trie trie = neuer Trie();
trie.insert(„Apfel“);
trie.search("apple"); // True zurückgeben
trie.search("app"); // False zurückgeben
trie.startsWith("app"); // True zurückgeben
trie.insert(„App“);
trie.search("app"); // True zurückgeben

Hinweis:

• 1 <= Wortlänge, Präfixlänge <= 2000
• Wort und Präfix bestehen nur aus englischen Kleinbuchstaben
• Die Gesamtzahl der Aufrufe „insert“, „search“ und „startsWith“ überschreitet nicht 3 * 10⁴ Zweitklassig

Präfixbaum

Ein Präfixbaum, auch Trie-Baum (ausgesprochen „try“) genannt, ist eine Datenstruktur zum Speichern von Zeichenfolgensammlungen, die ein schnelles Abrufen und Einfügen von Zeichenfolgen sowie Abfragen nach Zeichenfolgenpräfixen ermöglicht. Jeder Knoten des Präfixbaums stellt ein Präfix einer Zeichenfolge dar, und die untergeordneten Knoten jedes Knotens stellen alle möglichen Erweiterungen des Präfixes dar, die ein Zeichen hinzufügen.

• Eigenschaften von Präfixbäumen：
  • Raumeffizienz: Bei Zeichenfolgensammlungen mit einer großen Anzahl gemeinsamer Präfixe können Präfixbäume Speicherplatz sparen.
  • Zeiteffizienz: Die zeitliche Komplexität von Einfüge- und Suchvorgängen beträgt normalerweise O(m), wobei m die Länge der Zeichenfolge ist.
  • dynamische Sammlung: Der Präfixbaum kann Zeichenfolgen dynamisch einfügen und löschen, was für Szenarien geeignet ist, die häufige Aktualisierungen erfordern.
• Grundlegende Operationen von Präfixbäumen：
  • einfügen: Fügen Sie eine Zeichenfolge in den Baum ein, beginnend beim Wurzelknoten und zeichenweise nach unten. Wenn der dem Zeichen entsprechende untergeordnete Knoten nicht vorhanden ist, erstellen Sie einen neuen Knoten.
  • suchen: Suchen Sie, ob eine Zeichenfolge im Baum vorhanden ist, beginnend beim Wurzelknoten und zeichenweise nach unten. Wenn der untergeordnete Knoten eines Zeichens nicht vorhanden ist, schlägt die Suche fehl.
  • Präfixsuche: Überprüft, ob eine Zeichenfolge mit einer bestimmten Zeichenfolge als Präfix vorhanden ist, ähnlich wie bei der Suchoperation, muss jedoch nicht das Endflag des letzten Knotens überprüfen.
  • löschen: Das Löschen einer Zeichenfolge aus einem Baum erfordert das rekursive Löschen von Knoten. Dabei muss sichergestellt werden, dass gemeinsame Präfixknoten anderer Zeichenfolgen nicht gelöscht werden.
• Anwendungsszenarien des Präfixbaums：
  • automatische Vervollständigung: Stellen Sie in Suchmaschinen oder Texteditoren schnell Vervollständigungsvorschläge basierend auf den vom Benutzer eingegebenen Präfixen bereit.
  • Rechtschreibprüfung: Prüft, ob das vom Benutzer eingegebene Wort richtig geschrieben ist und liefert Vorschläge zur korrekten Schreibweise.
  • IP-Routing: In einem Netzwerk wird der längste Präfixabgleich verwendet, um den Routing-Pfad eines Pakets zu bestimmen.
  • Gensequenzanalyse: Wird in der Bioinformatik verwendet, um Gensequenzen schnell abzugleichen und abzurufen.

Antwort

1. Ideen zur Problemlösung：

Ein Trie (Präfixbaum) ist eine Baumdatenstruktur, die zum schnellen Abrufen von Schlüsseln in einem String-Datensatz verwendet wird. Es handelt sich um eine besondere Art von Baum, in dem jeder Knoten ein Zeichen darstellt und der Pfad von der Wurzel zu einem Knoten eine Zeichenfolge darstellt. Trie-Bäume werden häufig verwendet, um Funktionen wie automatische Vervollständigung und Rechtschreibprüfung zu implementieren.

Im Folgenden sind die grundlegenden Schritte und Problemlösungsideen für die Implementierung eines Trie-Baums aufgeführt:

1. Definieren Sie Trie-Knoten：

   • Jeder Trie-Knoten enthält normalerweise eine Reihe von Zeichen oder einen booleschen Wert, um das Ende des Wortes darzustellen, sowie Zeiger auf untergeordnete Knoten.

2. Versuch initialisieren：

   • Erstellen Sie einen Wurzelknoten, der keine Zeichen enthält, aber als Ausgangspunkt für alle Wörter dient.

3. Einfügevorgang：

   • Ausgehend vom Wurzelknoten gilt für jedes einzufügende Zeichen in der Zeichenfolge Folgendes:
     • Wenn der dem Zeichen entsprechende untergeordnete Knoten nicht vorhanden ist, erstellen Sie einen neuen untergeordneten Knoten.
     • Verschieben Sie den aktuellen Knoten auf den entsprechenden untergeordneten Knoten.

4. Suchvorgang：

   • Beginnen Sie mit dem Wurzelknoten und führen Sie für jedes Zeichen in der Zeichenfolge, nach dem Sie suchen möchten, Folgendes aus:
     • Wenn der dem Zeichen entsprechende untergeordnete Knoten vorhanden ist, setzen Sie die Suche fort.
     • Wenn es nicht vorhanden ist, wird ein Suchfehler zurückgegeben.

5. Präfixsuche：

   • Ähnlich wie bei der Suchoperation, es wird jedoch nur darauf geachtet, ob das Präfix der Zeichenfolge vorhanden ist.

6. Vorgang löschen(Optional):

   • Implementieren Sie die Möglichkeit, Wörter nach Bedarf zu löschen. Dies erfordert normalerweise das Löschen von Knoten und erfordert die Handhabung des Referenzzählers des Knotens.

7. Autocomplete-Funktion(Optional):

   • Gibt bei gegebenem Präfix alle Zeichenfolgen zurück, die mit diesem Präfix beginnen.

2. C++-Demo：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• Ausgabeergebnis:

1
0
1

3. Code-Lageradresse：Trie