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.
Versuche sind ideal in Szenarien, in denen Folgendes erforderlich ist:
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.
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
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!