So implementieren Sie einen Präfixbaum in Java

1. Präfixbaum

1. Was ist ein Präfixbaum?

Wörterbuchbaum (Trie-Baum) ist eine baumförmige Datenstruktur, die häufig zur Speicherung verwendet wird von Zeichenfolgen und Suche. Die Kernidee des Wörterbuchbaums besteht darin, gemeinsame Präfixe zwischen Zeichenfolgen zu verwenden, um Speicherplatz zu sparen und die Abfrageeffizienz zu verbessern. Es handelt sich um einen Mehrbaum, jeder Knoten stellt das Präfix einer Zeichenfolge dar und der Pfad vom Wurzelknoten zum Blattknoten bildet eine Zeichenfolge.

Der Wurzelknoten des Wörterbuchbaums enthält keine Zeichen. Jeder untergeordnete Knoten stellt ein Zeichen dar. Die Zeichen auf dem Pfad vom Wurzelknoten zu einem beliebigen Knoten sind mit der durch den Knoten dargestellten Zeichenfolge verbunden. Jeder Knoten kann eine oder mehrere Zeichenfolgen speichern, wobei normalerweise ein Flag verwendet wird, um zu markieren, ob die durch einen Knoten dargestellte Zeichenfolge vorhanden ist. Wenn Sie eine Zeichenfolge in einer Reihe von Zeichenfolgen finden müssen, können Sie mithilfe eines Wörterbuchbaums effiziente Suchvorgänge durchführen.

2. Beispiel für einen Präfixbaum

Erstellen Sie beispielsweise ein Präfix für das String-Array {"goog", "google", "bai", "baidu", " a"} Baum, zu diesem Zeitpunkt können wir einige Merkmale des Präfixbaums deutlich erkennen:

• Der Wurzelknoten speichert keine Zeichen

#🎜🎜 #
• Der Präfixbaum ist ein Multi-Fork-Baum

• Jeder Knoten des Präfixbaums speichert ein Zeichen

• Strings mit demselben Präfix werden auf demselben Pfad gespeichert

• Das Ende des Strings hat auch ein Endzeichen im Präfixbaum# 🎜🎜 #

2. Implementierung des Präfixbaums

Frage 208 zu Liqun ist die Implementierung des Präfixes Baum: Likou

1. Datenstruktur des Präfixbaums

Beim Schreiben von Code verwende ich lieber Hash-Tabellen zum Speichern von Knoteninformationen, und einige können auch verwendet werden Arrays werden verwendet um Knoteninformationen zu speichern. #4. Präfixe finden

public class Trie {
    Map<Character, Trie> next;
    boolean isEnd;
    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }
    public void insert(String word) {
    }
    public boolean search(String word) {
        return false;
    }
    public boolean startsWith(String prefix) {
        return false;
    }
}

Der nächste Schritt besteht darin, einige Fragen zu Präfixbäumen zu stellen

3 das Wörterbuch

1. Fragenbeschreibung

Geben Sie ein String-Array

und fügen Sie nach und nach einen Buchstaben zu anderen Wörtern im Wörterbuch hinzu.

Wenn es mehrere mögliche Antworten gibt, wird das Wort mit der kleinsten lexikografischen Reihenfolge unter den Antworten zurückgegeben. Erfolgt keine Antwort, wird ein leerer String zurückgegeben.

利克:利狠

2. Problemanalyse

Dies ist ein typisches Präfixbaumproblem, aber diese Frage erfordert einige spezielle Funktionen Die zurückgegebene Antwort lautet: words 组成的一本英语词典。返回words 中最长的一个单词，该单词是由words

1 Das längste Wort

2 Dieses Wort setzt sich nach und nach aus anderen Wörtern zusammen.

3 kleinste Wörterbuchreihenfolge

Daher müssen wir den relevanten Code des Präfixbaums ändern. Der Code zum Einfügen von Zeichenfolgen bleibt unverändert. Die Hauptänderung ist der Suchcode, der im Versuch enthalten sein sollte .next.get(c) == null fügt eine Bedingung hinzu, die als falsch beurteilt werden soll, das heißt, jeder Knoten sollte ein Flag „true“ haben, das angibt, dass in jedem Knoten ein Wort vorhanden ist, und schließlich den längsten Wortschritt (Blatt) bilden Schritt für Schritt Das Wort des Knotens)

3. Code-Implementierung

    public void insert(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                trie.next.put(c, new Trie());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        trie.isEnd = true;
    }

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Präfixbaum in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!