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.
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
2. Implementierung des Präfixbaums
1. Datenstruktur des Präfixbaums
public class Trie { Map 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-ArrayWenn 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.
Dies ist ein typisches Präfixbaumproblem, aber diese Frage erfordert einige spezielle Funktionen Die zurückgegebene Antwort lautet:words组成的一本英语词典。返回words中最长的一个单词，该单词是由words
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!
