Lupakan Semua Yang Anda Tahu Tentang Pencarian Rentetan - Percubaan Akan Meredakan Fikiran Anda!

Pengenalan kepada Trie Data Structure

Cuba, juga dikenali sebagai pepohon awalan, ialah struktur data seperti pepohon yang cekap digunakan untuk menyimpan dan mendapatkan semula rentetan. Ia amat berguna untuk tugasan yang melibatkan carian rentetan, padanan awalan dan kefungsian autolengkap.

Sebutan:

• Ia adalah perkataan suku kata tunggal
• "iaitu" pada penghujungnya disebut sebagai bunyi "e" yang panjang, serupa dengan "lihat" atau "pokok"
• Ia tidak berima dengan "pai" atau "mati" Sebutan ini membantu membezakannya daripada perkataan lain yang kelihatan serupa dan menekankan kaitannya dengan operasi mendapatkan data.

Bila Menggunakan Trie

Percubaan sesuai dalam senario yang anda perlukan:

1. Lakukan carian berasaskan awalan dengan cepat
2. Laksanakan ciri autolengkap
3. Simpan kamus perkataan untuk semakan ejaan
4. Simpan dan dapatkan semula rentetan dengan awalan biasa dengan cekap ## Menggambarkan Percubaan

Mari kita bayangkan percubaan yang mengandungi perkataan "kucing", "kereta" dan "anjing":

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

Setiap nod mewakili aksara, dan laluan dari akar ke nod daun membentuk perkataan yang lengkap.

Melaksanakan Percubaan dalam JavaScript

Mari kita laksanakan struktur percubaan asas dalam JavaScript:

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

Penjelasan Kod

1. kelas TrieNode: Mewakili nod dalam trie. Setiap nod mempunyai:: Objek untuk menyimpan nod anak: Bendera boolean untuk menandakan penghujung perkataan
2. Kelas Percubaan: Struktur percubaan utama dengan kaedah:
   • sisipan: Menambah perkataan pada percubaan
   • carian: Menyemak sama ada perkataan wujud dalam percubaan
   • bermula Dengan: Menyemak sama ada mana-mana perkataan dalam percubaan bermula dengan awalan yang diberikan
3. Kaedah merentasi trie, mencipta nod baharu untuk aksara yang tidak wujud dan menandakan nod terakhir sebagai penghujung perkataan.
4. Kaedah ini merentasi percubaan di sepanjang laluan perkataan yang diberikan, kembali jika keseluruhan perkataan ditemui dan ditandakan sebagai perkataan yang lengkap.
5. Kaedahnya serupa dengan tetapi hanya menyemak sama ada awalan yang diberikan wujud dalam trie, tidak kira sama ada itu perkataan yang lengkap.

Kerumitan Masa dan Ruang

• Kerumitan Masa:
  • Sisipkan: O(m), dengan m ialah panjang perkataan
  • Cari: O(m), dengan m ialah panjang perkataan
  • Bermula Dengan: O(m), dengan m ialah panjang awalan
• Kerumitan Ruang:O(n * m), dengan n ialah bilangan perkataan dan m ialah purata panjang perkataan

Tries menawarkan prestasi cemerlang untuk operasi berkaitan rentetan, terutamanya apabila berurusan dengan set besar perkataan dengan awalan biasa. Ia menyediakan carian pantas dan padanan awalan, menjadikannya tidak ternilai dalam pelbagai aplikasi seperti sistem autolengkap, jadual penghalaan IP dan pelaksanaan kamus.

Jika anda menyukai tutorial ini ikuti saya di sini dan di X/Twitter di @turckalicious. Artikel ini dibuat dengan bantuan Wonderfall (https://wonderfall.xyz), penyunting dokumen interaktif dikuasakan AI yang membantu anda menyelidik, menulis dan mengulang dengan lebih pantas.

Atas ialah kandungan terperinci Lupakan Semua Yang Anda Tahu Tentang Pencarian Rentetan - Percubaan Akan Meredakan Fikiran Anda!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!