Teknologian jakaminen

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

原题链接🔗：Toteuta Trie (etuliitepuu)
vaikeus: Keskikokoinen⭐️⭐️

aihe

Trie (lausutaan "yritä") tai etuliite puu Onko puutietorakenne, jota käytetään avaimien tehokkaaseen tallentamiseen ja hakemiseen merkkijonotietojoukossa. Tällä tietorakenteella on useita käyttötapauksia, kuten automaattinen täydennys ja oikeinkirjoituksen tarkistus.

Ota käyttöön Trie-luokka:

• Trie() Alusta etuliitepuuobjekti.
• void insert(String word) Lisää merkkijono etuliitepuuhunword 。
• boolean search(String word) jos merkkijonoword Palaa etuliitepuussa true(eli on lisätty ennen hakua, muussa tapauksessa palauttaa). false 。
• boolean startsWith(String prefix) Jos merkkijono on lisätty aiemmin wordYksi etuliitteistä on prefix ,palata true ; muussa tapauksessa palautafalse。

Esimerkki:

tulla sisään
Trie insert search search startsWith insert search
[] ["omena"] ["omena"] ["sovellus"] ["sovellus"] ["sovellus"] ["sovellus"]
ulostulo
[null, null, true, false, true, nolla, true]

selittää
Trie trie = uusi Trie();
trie.insert("omena");
trie.search("omena"); // Return True
trie.search("app"); // Palauta False
trie.startsWith("app"); // Return True
try.insert("sovellus");
trie.search("app"); // Return True

vihje:

• 1 <= sana.pituus, etuliite.pituus <= 2000
• sana ja etuliite koostuvat vain englannin pienistä kirjaimista
• Lisäysten, hakujen ja puhelujen kanssa aloitusten kokonaismäärä ei ylitä 3 * 10⁴ Toisen luokan

etuliite puu

Etuliitepuu, joka tunnetaan myös nimellä Trie-puu (lausutaan "try"), on tietorakenne, jota käytetään merkkijonokokoelmien tallentamiseen ja joka mahdollistaa merkkijonojen nopean haun ja lisäämisen sekä merkkijonojen etuliitteiden kyselyt. Jokainen etuliitepuun solmu edustaa merkkijonon etuliitettä, ja kunkin solmun lapset edustavat kaikkia mahdollisia etuliitteen laajennuksia, jotka lisäävät yhden merkin.

• Etuliitepuiden ominaisuudet：
  • tilatehokkuutta: Merkkijonokokoelmissa, joissa on suuri määrä yhteisiä etuliitteitä, etuliitepuut voivat säästää tallennustilaa.
  • ajan tehokkuus: Lisäys- ja hakutoimintojen aikamonimutkaisuus on yleensä O(m), missä m on merkkijonon pituus.
  • dynaaminen kokoelma: Etuliitepuu voi dynaamisesti lisätä ja poistaa merkkijonoja, mikä sopii tilanteisiin, jotka vaativat usein päivityksiä.
• Etuliitepuiden perustoiminnot：
  • lisää: Lisää merkkijono puuhun alkaen juurisolmusta ja alaspäin merkki kerrallaan. Jos merkkiä vastaavaa lapsisolmua ei ole olemassa, luo uusi solmu.
  • Hae: Etsi, onko puussa merkkijonoa alkaen juurisolmusta ja siirtymällä alaspäin merkki kerrallaan. Jos merkin alisolmua ei ole olemassa, haku epäonnistuu.
  • Etuliitehaku: Tarkistaa, onko jonkin tietyn merkkijonon edessä merkkijonoa, kuten hakuoperaatiossa, mutta ei tarvitse tarkistaa viimeisen solmun loppulippua.
  • poistaa: Merkkijonon poistaminen puusta edellyttää solmujen poistamista rekursiivisesti varmistaen samalla, että muiden merkkijonojen yhteisiä etuliitesolmuja ei poisteta.
• Etuliitepuun sovellusskenaariot：
  • automaattinen täydennys: Anna hakukoneissa tai tekstieditoreissa nopeasti täydennysehdotuksia käyttäjän syöttämien etuliitteiden perusteella.
  • Oikeinkirjoituksen tarkistus: Tarkistaa, onko käyttäjän kirjoittama sana kirjoitettu oikein, ja antaa oikeinkirjoitusehdotuksia.
  • IP-reititys: Verkossa pisintä etuliitesovitusta käytetään määrittämään paketin reitityspolku.
  • Geenisekvenssianalyysi: Bioinformatiikassa käytetään geenisekvenssien nopeaan sovittamiseen ja hakemiseen.

vastaus

1. Ideoita ongelmanratkaisuun：

Trie (etuliitepuu) on puutietorakenne, jota käytetään avainten nopeaan hakemiseen merkkijonotietojoukosta. Se on erityinen puu, jossa jokainen solmu edustaa merkkiä ja polku juuresta solmuun edustaa merkkijonoa. Trie-puita käytetään usein toteuttamaan toimintoja, kuten automaattinen täydennys ja oikeinkirjoituksen tarkistus.

Seuraavassa on perusvaiheet ja ongelmanratkaisuideat Trie-puun toteuttamiseksi:

1. Määritä Trie-solmut：

   • Jokainen Trie-solmu sisältää yleensä joukon merkkejä tai Boolen arvon, joka edustaa sanan loppua, ja osoittimia lapsisolmuihin.

2. Alusta Trie：

   • Luo juurisolmu, joka ei sisällä merkkejä, mutta toimii kaikkien sanojen lähtökohtana.

3. insert-toiminto：

   • Aloittaen juurisolmusta, jokaiselle lisättävän merkkijonon merkille:
     • Jos merkkiä vastaavaa lapsisolmua ei ole olemassa, luo uusi lapsisolmu.
     • Siirrä nykyinen solmu vastaavaan lapsisolmuun.

4. Hakutoiminto：

   • Aloittaen juurisolmusta, jokaiselle merkkijonolle, jota haluat etsiä:
     • Jos merkkiä vastaava lapsisolmu on olemassa, jatka hakua.
     • Jos sitä ei ole, palautetaan hakuvirhe.

5. Etuliitehaku：

   • Samanlainen kuin hakutoiminto, mutta välittää vain siitä, onko merkkijonon etuliite olemassa.

6. Poista toiminto(valinnainen):

   • Ota käyttöön mahdollisuus poistaa sanoja tarpeen mukaan, mikä yleensä sisältää solmujen poistamisen ja vaatii solmun viitemäärän käsittelyä.

7. Automaattinen täydennystoiminto(valinnainen):

   • Anna etuliite, palauta kaikki tällä etuliitteellä alkavat merkkijonot.

2. c++ demo：

#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

• Tulostustulos:

1
0
1

3. Koodivaraston osoite：Trie