Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

原题链接🔗：Implementasikan Trie (pohon awalan)
kesulitan: Sedang⭐️⭐️

tema

Trie (diucapkan seperti "coba") atau pohon awalan Adalah struktur data pohon yang digunakan untuk menyimpan dan mengambil kunci secara efisien dalam kumpulan data string. Struktur data ini memiliki beberapa kasus penggunaan, seperti pelengkapan otomatis dan pemeriksaan ejaan.

Silakan terapkan kelas Trie:

• Trie() Inisialisasi objek pohon awalan.
• void insert(String word) Masukkan string ke dalam pohon awalanword 。
• boolean search(String word) jika stringword Di pohon awalan, kembali true(yaitu, telah dimasukkan sebelum pengambilan); jika tidak, akan dikembalikan false 。
• boolean startsWith(String prefix) Jika string telah dimasukkan sebelumnya wordSalah satu awalannya adalah prefix ,kembali true ; Jika tidak, kembalikanfalse。

Contoh:

memasuki
[“Coba”, “masukkan”, “cari”, “cari”, “dimulaiDengan”, “masukkan”, “cari”]
[[], [“apel”], [“apel”], [“aplikasi”], [“aplikasi”], [“aplikasi”], [“aplikasi”]]
keluaran
[null, null, benar, salah, benar, null, benar]

menjelaskan
Trie trie = new Trie();
trie.insert(“apel”);
trie.search("apel"); // Mengembalikan Benar
trie.search("aplikasi"); // Kembalikan Salah
trie.startsWith("aplikasi"); // Kembalikan Benar
trie.insert(“aplikasi”);
trie.search("aplikasi"); // Mengembalikan Benar

petunjuk:

• 1 <= panjang kata, panjang awalan <= 2000
• kata dan awalan hanya terdiri dari huruf kecil bahasa Inggris
• Jumlah total panggilan penyisipan, pencarian, dan startWith tidak melebihi 3 * 10⁴ Kelas dua

pohon awalan

Pohon awalan, juga dikenal sebagai pohon Trie (diucapkan "coba"), adalah struktur data yang digunakan untuk menyimpan kumpulan string, yang memungkinkan pengambilan dan penyisipan string dengan cepat, serta kueri untuk awalan string. Setiap node dari pohon awalan mewakili awalan dari sebuah string, dan anak dari setiap node mewakili semua kemungkinan ekstensi dari awalan yang menambahkan satu karakter.

• Karakteristik pohon awalan：
  • efisiensi ruang: Untuk koleksi string dengan banyak awalan umum, pohon awalan dapat menghemat ruang penyimpanan.
  • efisiensi waktu: Kompleksitas waktu operasi penyisipan dan pencarian biasanya O(m), dimana m adalah panjang string.
  • koleksi dinamis: Pohon awalan dapat menyisipkan dan menghapus string secara dinamis, yang cocok untuk skenario yang memerlukan pembaruan rutin.
• Operasi dasar pohon awalan：
  • menyisipkan: Memasukkan string ke dalam pohon, dimulai dari simpul akar dan turun karakter demi karakter. Jika simpul anak yang sesuai dengan karakter tersebut tidak ada, buatlah simpul baru.
  • mencari: Mencari apakah suatu string ada di pohon, dimulai dari simpul akar dan turun karakter demi karakter. Jika simpul anak dari suatu karakter tidak ada, pencarian gagal.
  • Pencarian awalan: Memeriksa apakah ada string yang diawali dengan string tertentu, mirip dengan operasi pencarian, tetapi tidak perlu memeriksa tanda akhir dari node terakhir.
  • menghapus: Menghapus string dari pohon memerlukan penghapusan node secara rekursif sambil memastikan bahwa node awalan umum dari string lain tidak dihapus.
• Skenario penerapan pohon awalan：
  • Pelengkapan otomatis: Di mesin pencari atau editor teks, berikan saran penyelesaian dengan cepat berdasarkan awalan yang dimasukkan oleh pengguna.
  • Cek ejaan: Memeriksa apakah kata yang dimasukkan oleh pengguna dieja dengan benar dan memberikan saran ejaan yang benar.
  • Perutean IP: Dalam suatu jaringan, pencocokan awalan terpanjang digunakan untuk menentukan jalur perutean suatu paket.
  • Analisis urutan gen: Dalam bioinformatika, digunakan untuk mencocokkan dan mengambil urutan gen dengan cepat.

menjawab

1. Ide pemecahan masalah：

Trie (pohon awalan) adalah struktur data pohon yang digunakan untuk pengambilan kunci dengan cepat dalam kumpulan data string. Ini adalah jenis pohon khusus di mana setiap node mewakili karakter dan jalur dari akar ke node mewakili string. Pohon trie sering digunakan untuk mengimplementasikan fungsi seperti penyelesaian otomatis dan pemeriksaan ejaan.

Berikut ini adalah langkah-langkah dasar dan ide pemecahan masalah dalam penerapan pohon Trie:

1. Tentukan node Trie：

   • Setiap node Trie biasanya berisi sekumpulan karakter atau nilai Boolean untuk mewakili akhir kata, dan penunjuk ke node anak.

2. Inisialisasi Trie：

   • Buat simpul akar yang tidak berisi karakter tetapi berfungsi sebagai titik awal untuk semua kata.

3. operasi penyisipan：

   • Dimulai dari node root, untuk setiap karakter dalam string yang akan disisipkan:
     • Jika node anak yang sesuai dengan karakter tersebut tidak ada, buatlah node anak baru.
     • Pindahkan node saat ini ke node anak yang sesuai.

4. Operasi pencarian：

   • Dimulai dari node root, untuk setiap karakter dalam string yang ingin dicari:
     • Jika node anak yang sesuai dengan karakter tersebut ada, lanjutkan pencarian.
     • Jika tidak ada, kegagalan pencarian akan dikembalikan.

5. Pencarian awalan：

   • Mirip dengan operasi pencarian, tetapi hanya peduli apakah awalan string ada.

6. Hapus operasi(opsional):

   • Menerapkan kemampuan untuk menghapus kata sesuai kebutuhan, yang biasanya melibatkan penghapusan node, dan memerlukan penanganan jumlah referensi node.

7. Fungsi pelengkapan otomatis(opsional):

   • Diberi awalan, kembalikan semua string yang dimulai dengan awalan itu.

2. demonstrasi c++：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• Hasil keluaran:

1
0
1

3. Kode alamat gudang：Percobaan