Vergessen Sie alles, was Sie über die Suche nach Zeichenfolgen wissen – Versuche werden Sie umhauen!

Einführung in die Trie-Datenstruktur

Ein Trie, auch Präfixbaum genannt, ist eine effiziente baumartige Datenstruktur, die zum Speichern und Abrufen von Zeichenfolgen verwendet wird. Dies ist besonders nützlich für Aufgaben mit Zeichenfolgensuche, Präfixabgleich und Autovervollständigungsfunktion.

Aussprache:

• Es ist ein einsilbiges Wort
• Das „ie“ am Ende wird als langer „e“-Laut ausgesprochen, ähnlich wie „see“ oder „tree“
• Es reimt sich nicht auf „pie“ oder „die“ Diese Aussprache hilft, es von anderen ähnlich aussehenden Wörtern zu unterscheiden und betont seinen Zusammenhang mit Datenabrufvorgängen.

Wann sollte ein Versuch verwendet werden?

Versuche sind ideal in Szenarien, in denen Folgendes erforderlich ist:

1. Führen Sie schnell präfixbasierte Suchen durch
2. Autovervollständigungsfunktionen implementieren
3. Speichern Sie ein Wörterbuch mit Wörtern zur Rechtschreibprüfung
4. Effizientes Speichern und Abrufen von Zeichenfolgen mit gemeinsamen Präfixen ## Einen Versuch visualisieren

Stellen wir uns einen Versuch vor, der die Wörter „Katze“, „Auto“ und „Hund“ enthält:

       root
     /   |   \
    c    d    ...
   /     |
  a      o
 / \     |
t   r    g

Jeder Knoten stellt ein Zeichen dar und die Pfade vom Wurzel- zum Blattknoten bilden vollständige Wörter.

Implementierung eines Versuchs in JavaScript

Lassen Sie uns eine grundlegende Trie-Struktur in JavaScript implementieren:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insert a word into the trie
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  // Check if any word starts with the given prefix
  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

// Example usage
const trie = new Trie();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: true
console.log(trie.search("appl"));     // Output: false
console.log(trie.startsWith("app"));  // Output: true
console.log(trie.startsWith("ban"));  // Output: true
console.log(trie.startsWith("cat"));  // Output: false

Erläuterung des Kodex

1. Klasse TrieNode: Stellt einen Knoten im Trie dar. Jeder Knoten verfügt über: Ein Objekt zum Speichern untergeordneter Knoten: Ein boolesches Flag zum Markieren des Endes eines Wortes
2. Klasse Trie: Die Haupt-Trie-Struktur mit Methoden:
   • Einfügen: Fügt dem Versuch ein Wort hinzu
   • Suche: Prüft, ob ein Wort im Versuch vorhanden ist
   • startsWith: Prüft, ob ein Wort im Versuch mit dem angegebenen Präfix beginnt
3. Die Methode durchläuft den Versuch, erstellt neue Knoten für nicht vorhandene Zeichen und markiert den letzten Knoten als Ende eines Wortes.
4. Die Methode durchläuft den Versuch entlang des Pfads des angegebenen Worts und kehrt zurück, wenn das gesamte Wort gefunden und als vollständiges Wort markiert wurde.
5. Die Methode ähnelt der Methode, prüft jedoch nur, ob das angegebene Präfix im Versuch vorhanden ist, unabhängig davon, ob es sich um ein vollständiges Wort handelt.

Zeit- und Raumkomplexität

• Zeitkomplexität:
  • Fügen Sie ein: O(m), wobei m die Länge des Wortes ist
  • Suche: O(m), wobei m die Länge des Wortes ist
  • StartsWith: O(m), wobei m die Länge des Präfixes ist
• Raumkomplexität:O(n * m), wobei n die Anzahl der Wörter und m die durchschnittliche Länge der Wörter ist

Versuche bieten eine hervorragende Leistung für stringbezogene Operationen, insbesondere wenn es um eine große Menge von Wörtern mit gemeinsamen Präfixen geht. Sie bieten schnelle Suchvorgänge und Präfixabgleiche, was sie in verschiedenen Anwendungen wie Autovervollständigungssystemen, IP-Routing-Tabellen und Wörterbuchimplementierungen von unschätzbarem Wert macht.

Wenn Ihnen dieses Tutorial gefallen hat, folgen Sie mir hier und auf X/Twitter unter @turckalicious. Dieser Artikel wurde mit Hilfe von Wonderfall (https://wonderfall.xyz) erstellt, einem KI-gestützten interaktiven Dokumenteneditor, der Ihnen hilft, schneller zu recherchieren, zu schreiben und zu iterieren.

Das obige ist der detaillierte Inhalt vonVergessen Sie alles, was Sie über die Suche nach Zeichenfolgen wissen – Versuche werden Sie umhauen!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!