Κοινή χρήση τεχνολογίας

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

原题链接🔗：Εφαρμογή Trie (δέντρο προθέματος)
δυσκολία: Μεσαίο⭐️⭐️

θέμα

Trie (προφέρεται σαν "δοκιμάζω") ή δέντρο προθέματος Είναι μια δομή δεδομένων δέντρου που χρησιμοποιείται για την αποτελεσματική αποθήκευση και ανάκτηση κλειδιών σε ένα σύνολο δεδομένων συμβολοσειρών. Αυτή η δομή δεδομένων έχει αρκετές περιπτώσεις χρήσης, όπως η αυτόματη συμπλήρωση και ο ορθογραφικός έλεγχος.

Παρακαλούμε εφαρμόστε την κλάση Trie:

• Trie() Αρχικοποιήστε το αντικείμενο δέντρου του προθέματος.
• void insert(String word) Εισαγάγετε συμβολοσειρά στο δέντρο προθέματοςword 。
• boolean search(String word) αν χορδήword Στο δέντρο του προθέματος, επιστροφή true(δηλαδή, έχει εισαχθεί πριν από την ανάκτηση), διαφορετικά, επιστρέφει false 。
• boolean startsWith(String prefix) Εάν η συμβολοσειρά έχει εισαχθεί προηγουμένως wordΈνα από τα προθέματα είναι prefix ,ΕΠΙΣΤΡΟΦΗ true Διαφορετικά, επιστρέψτεfalse。

Παράδειγμα:

εισαγω
Δοκιμή εισαγωγή αναζήτηση αναζήτηση startsWith εισαγωγή αναζήτηση
[] ["μήλο"] ["μήλο"] ["εφαρμογή"] ["εφαρμογή"] ["εφαρμογή"] ["εφαρμογή"]
παραγωγή
[μηδενική, μηδενική, αληθής, ψευδής, αληθής, μηδενική, αληθής]

εξηγώ
Trie trie = new Trie();
trye.insert("μήλο");
trye.search("apple") // Return True
trye.search("app");
trye.startsWith("app") // Return True
trie.insert("εφαρμογή");
trye.search("app");

ίχνος:

• 1 <= word.length, prefix.length <= 2000
• λέξη και πρόθεμα αποτελούνται μόνο από πεζά αγγλικά γράμματα
• Ο συνολικός αριθμός των κλήσεων εισαγωγής, αναζήτησης και εκκινήσεων με κλήσεις δεν υπερβαίνει τα 3 * 10⁴ Δεύτερης διαλογής

δέντρο προθέματος

Ένα δέντρο προθέματος, γνωστό και ως δέντρο Trie (προφέρεται "try"), είναι μια δομή δεδομένων που χρησιμοποιείται για την αποθήκευση συλλογών συμβολοσειρών, η οποία επιτρέπει γρήγορη ανάκτηση και εισαγωγή συμβολοσειρών, καθώς και ερωτήματα για προθέματα συμβολοσειρών. Κάθε κόμβος του δέντρου προθέματος αντιπροσωπεύει ένα πρόθεμα μιας συμβολοσειράς και τα παιδιά κάθε κόμβου αντιπροσωπεύουν όλες τις πιθανές επεκτάσεις του προθέματος που προσθέτουν έναν χαρακτήρα.

• Χαρακτηριστικά των δέντρων προθέματος：
  • αποδοτικότητα χώρου: Για συλλογές συμβολοσειρών με μεγάλο αριθμό κοινών προθεμάτων, τα δέντρα προθέματος μπορούν να εξοικονομήσουν χώρο αποθήκευσης.
  • αποτελεσματικότητα χρόνου: Η χρονική πολυπλοκότητα των εργασιών εισαγωγής και αναζήτησης είναι συνήθως O(m), όπου m είναι το μήκος της συμβολοσειράς.
  • δυναμική συλλογή: Το δέντρο προθέματος μπορεί να εισάγει και να διαγράφει δυναμικά συμβολοσειρές, κάτι που είναι κατάλληλο για σενάρια που απαιτούν συχνές ενημερώσεις.
• Βασικές λειτουργίες των δέντρων προθέματος：
  • εισάγετε: Εισαγάγετε μια συμβολοσειρά στο δέντρο, ξεκινώντας από τον ριζικό κόμβο και κατεβαίνοντας χαρακτήρα προς χαρακτήρα Αν ο θυγατρικός κόμβος που αντιστοιχεί στον χαρακτήρα δεν υπάρχει, δημιουργήστε έναν νέο κόμβο.
  • Αναζήτηση: Αναζητήστε εάν υπάρχει συμβολοσειρά στο δέντρο, ξεκινώντας από τον ριζικό κόμβο και κατεβαίνοντας χαρακτήρα προς χαρακτήρα Εάν ο θυγατρικός κόμβος ενός χαρακτήρα δεν υπάρχει, η αναζήτηση αποτυγχάνει.
  • Αναζήτηση προθέματος: Ελέγχει εάν υπάρχει κάποια συμβολοσειρά με πρόθεμα μιας συγκεκριμένης συμβολοσειράς, παρόμοια με τη λειτουργία αναζήτησης, αλλά δεν χρειάζεται να ελέγξει τη σημαία τέλους του τελευταίου κόμβου.
  • διαγράφω: Η διαγραφή μιας συμβολοσειράς από ένα δέντρο απαιτεί τη διαγραφή κόμβων αναδρομικά, διασφαλίζοντας παράλληλα ότι δεν διαγράφονται οι κοινοί κόμβοι προθέματος άλλων συμβολοσειρών.
• Σενάρια εφαρμογής του δέντρου προθέματος：
  • αυτόματη συμπλήρωση: Σε μηχανές αναζήτησης ή προγράμματα επεξεργασίας κειμένου, παρέχετε γρήγορα προτάσεις ολοκλήρωσης με βάση τα προθέματα που εισάγει ο χρήστης.
  • Ορθογραφικός έλεγχος: Ελέγχει εάν η λέξη που εισήγαγε ο χρήστης έχει γραφτεί σωστά και παρέχει σωστές προτάσεις ορθογραφίας.
  • Δρομολόγηση IP: Σε ένα δίκτυο, η μεγαλύτερη αντιστοίχιση προθέματος χρησιμοποιείται για τον προσδιορισμό της διαδρομής δρομολόγησης ενός πακέτου.
  • Ανάλυση γονιδιακής αλληλουχίας: Στη βιοπληροφορική, χρησιμοποιείται για γρήγορη αντιστοίχιση και ανάκτηση αλληλουχιών γονιδίων.

απάντηση

1. Ιδέες επίλυσης προβλημάτων：

Το Trie (δέντρο προθέματος) είναι μια δομή δεδομένων δέντρου που χρησιμοποιείται για γρήγορη ανάκτηση κλειδιών σε ένα σύνολο δεδομένων συμβολοσειρών. Είναι ένα ειδικό είδος δέντρου στο οποίο κάθε κόμβος αντιπροσωπεύει έναν χαρακτήρα και η διαδρομή από τη ρίζα σε έναν κόμβο αντιπροσωπεύει μια συμβολοσειρά. Τα δέντρα Trie χρησιμοποιούνται συχνά για την υλοποίηση λειτουργιών όπως η αυτόματη συμπλήρωση και ο ορθογραφικός έλεγχος.

Τα παρακάτω είναι τα βασικά βήματα και οι ιδέες επίλυσης προβλημάτων για την υλοποίηση ενός δέντρου Trie:

1. Ορισμός κόμβων Trie：

   • Κάθε κόμβος Trie περιέχει συνήθως ένα σύνολο χαρακτήρων ή μια τιμή Boolean για να αντιπροσωπεύει το τέλος της λέξης και δείκτες σε θυγατρικούς κόμβους.

2. Αρχικοποιήστε το Trie：

   • Δημιουργήστε έναν ριζικό κόμβο που δεν περιέχει χαρακτήρες αλλά χρησιμεύει ως αφετηρία για όλες τις λέξεις.

3. λειτουργία εισαγωγής：

   • Ξεκινώντας από τον ριζικό κόμβο, για κάθε χαρακτήρα στη συμβολοσειρά που θα εισαχθεί:
     • Εάν ο θυγατρικός κόμβος που αντιστοιχεί στον χαρακτήρα δεν υπάρχει, δημιουργήστε έναν νέο θυγατρικό κόμβο.
     • Μετακινήστε τον τρέχοντα κόμβο στον αντίστοιχο θυγατρικό κόμβο.

4. Λειτουργία αναζήτησης：

   • Ξεκινώντας από τον ριζικό κόμβο, για κάθε χαρακτήρα στη συμβολοσειρά που θέλετε να αναζητήσετε:
     • Εάν υπάρχει ο θυγατρικός κόμβος που αντιστοιχεί στον χαρακτήρα, συνεχίστε την αναζήτηση.
     • Εάν δεν υπάρχει, επιστρέφεται μια αποτυχία αναζήτησης.

5. Αναζήτηση προθέματος：

   • Παρόμοια με τη λειτουργία αναζήτησης, αλλά ενδιαφέρεται μόνο για το αν υπάρχει το πρόθεμα της συμβολοσειράς.

6. Λειτουργία διαγραφής(προαιρετικός):

   • Εφαρμόστε τη δυνατότητα διαγραφής λέξεων όπως απαιτείται, η οποία συνήθως περιλαμβάνει διαγραφή κόμβων και απαιτεί χειρισμό του αριθμού αναφοράς του κόμβου.

7. Λειτουργία αυτόματης συμπλήρωσης(προαιρετικός):

   • Με ένα πρόθεμα, επιστρέψτε όλες τις συμβολοσειρές που ξεκινούν με αυτό το πρόθεμα.

2. επίδειξη 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

• Αποτέλεσμα εξόδου:

1
0
1

3. Διεύθυνση αποθήκης κωδικού：Προσπάθησε