Bagaimana untuk melaksanakan pepohon awalan di Jawa

1. Pokok awalan

1. Apakah pokok awalan

Pokok kamus (pokok Trie) ialah struktur data pokok yang biasa digunakan untuk penyimpanan dan pencarian rentetan. Idea teras pokok kamus adalah menggunakan awalan biasa antara rentetan untuk menjimatkan ruang storan dan meningkatkan kecekapan pertanyaan. Ia adalah pokok berbilang, setiap nod mewakili awalan rentetan, dan laluan dari nod akar ke nod daun membentuk rentetan.

Nod akar pokok kamus tidak mengandungi aksara Setiap nod anak mewakili aksara. Setiap nod boleh menyimpan satu atau lebih rentetan, biasanya menggunakan bendera untuk menandakan sama ada rentetan yang diwakili oleh nod wujud. Apabila anda perlu mencari rentetan dalam satu set rentetan, anda boleh menggunakan pepohon kamus untuk mencapai operasi carian yang cekap.

2. Contoh pepohon awalan

Sebagai contoh, untuk mencipta pepohon awalan untuk tatasusunan rentetan {"goog", "google", "bai", "baidu", "a" }, pada masa ini Kita dapat melihat dengan jelas beberapa ciri pokok awalan:

• Nod akar tidak menyimpan aksara

• Pokok awalan ialah Pokok berbilang garpu

• Setiap nod pokok awalan menyimpan satu aksara

• Rentetan dengan awalan yang sama disimpan pada laluan yang sama

• Hujung rentetan juga mempunyai tanda akhir pada pokok awalan dengan sewajarnya

2. Pelaksanaan pepohon awalan

Soalan 208 tentang Likou adalah mengenai pelaksanaan pepohon awalan: Likou

1 Struktur data pepohon awalan

Apabila menulis kod, saya lebih suka untuk menggunakan pencincangan Jadual digunakan untuk menyimpan maklumat nod, dan sesetengahnya juga boleh menggunakan tatasusunan untuk menyimpan maklumat nod pada dasarnya adalah sama

public class Trie {
    Map<Character, Trie> 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;
    }
}

2 Sisipkan rentetan

    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;
    }

3

    public boolean search(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return trie.isEnd;
    }

4. Cari awalan

    public boolean startsWith(String prefix) {
        Trie trie = this;//获得根结点
        for (char c : prefix.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return true;
    }

Langkah seterusnya ialah menjawab beberapa soalan tentang pokok awalan

3. Perkataan terpanjang dalam kamus

1.Penerangan masalah

memberikan kamus bahasa Inggeris yang terdiri daripada tatasusunan rentetanwords. Mengembalikan perkataan terpanjang dalam words, yang terdiri daripada perkataan lain dalam kamus words dengan menambah satu huruf secara beransur-ansur.

Jika terdapat berbilang jawapan yang boleh dilaksanakan, kembalikan perkataan dengan susunan leksikografi terkecil antara jawapan. Jika tiada jawapan, rentetan kosong dikembalikan.

Liquou: Liquou

2 Analisis masalah

Ini adalah soalan pokok awalan biasa, tetapi soalan ini mempunyai beberapa keperluan khas, dan jawapannya adalah:

1. Perkataan terpanjang

2 Perkataan ini secara beransur-ansur terdiri daripada perkataan lain

3 Panjang yang sama mengembalikan leksikografi yang lebih kecil

Oleh itu, kita perlukan untuk mengubah suai kod yang berkaitan bagi pepohon awalan Kod untuk memasukkan rentetan satu demi satu tetap tidak berubah. Pengubahsuaian utama ialah kod carian ialah setiap nod harus mempunyai bendera true, menunjukkan bahawa terdapat satu perkataan dalam setiap nod, dan akhirnya perkataan terpanjang (perkataan nod daun) dibentuk langkah demi langkah

3 >rreeee

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pepohon awalan di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!