Trie (Prefiks Ağacı) Leetcode Həllini həyata keçirin

Problem bəyanat

The Trie (Prefiks Ağacı) LeetCode Həllini həyata keçirin – "Həyata keçirmək cəhd edin (Prefiks Ağacı)” sizdən yerinə yetirməyi xahiş edir Məlumat Strukturunu sınayın ifa edir inserting, axtarış və prefiks axtarışı səmərəli.

Misal:

Input:  ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output: [null, null, true, false, true, null, true]

Explanation:

• Bütün sətirləri daxil etdikdən sonra trie belə görünür.

Pin

• Söz alma mövcud olan axtarılır, buna görə də doğrudur.
• Söz app sonra daxil edilən axtarış edilir, ona görə də əvvəlcə yalan, sonra doğru nəticə verir.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas ideya yaratmaqdır Prefiks ağacı Trie məlumat strukturu adlanır.
2. Əvvəlcə iki əsas məlumatı saxlayacaq TrieNode sinfi yaradacağıq:
   1. Hər hansı bir söz bu qovşaqda bitər, yoxsa yox?
   2. Bütün qovşaqlar cari qovşaqdan çıxış edir.
3. Birincisi, edəcəyik kök nodu işə salın sınaqdan.
4. Daxiletmə sətirindəki hər simvol üçün, əgər mövcud deyilsə, cari simvolu ehtiva edən qovşağı daxil edəcəyik, əks halda sadəcə həmin qovluğa keçəcəyik. Simi trie daxil etdikdən sonra sətrin bitdiyi node kimi qeyd edəcəyik sonu = doğrudur.
5. Üçün tri-də simi axtarıre, kök qovşağından başlayaraq hər simvolu axtaracağıq. İstənilən addımda, növbəti node mövcud olmadıqda, yalanı qaytarın. Həmçinin, nəhayət, hər hansı bir sözün bu qovşaqda bitməli olub-olmadığını yoxlamaq lazımdır, əgər bəli, doğrudursa.
6. Üçün hər hansı bir prefiksi yoxlayır, hər simvol üçün bir-bir kök qovşağından keçməyə başlayın. İstənilən addımda, müəyyən bir node mövcud olmadıqda, yalanı qaytarın. Hər bir simvolu və mövcud olan hər bir nodu yoxladıqdan sonra, nəhayət, doğru qaytarın.

Kodu

Trie (Prefiks Ağacı) Leetcode C++ Həllini həyata keçirin:

class Trie {
public:
    struct TrieNode{
        bool end;
        vector<TrieNode*> child;
        TrieNode(){
            end = false;
            child.assign(26,nullptr);
        }
    };
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }
    void insert(string word) {
        TrieNode* curr = root;
        for(auto& c:word){
            if(!curr->child[c-'a']){
                curr->child[c-'a'] = new TrieNode();
            }
            curr = curr->child[c-'a'];
        }
        curr->end = true;
    }
    bool search(string word) {
        TrieNode* curr = root;
        for(auto& c:word){
            if(!curr->child[c-'a']){
                return false;
            }
            curr = curr->child[c-'a'];
        }
        return curr->end;
    }
    bool startsWith(string prefix) {
        TrieNode* curr = root;
        for(auto& c:prefix){
            if(!curr->child[c-'a']){
                return false;
            }
            curr = curr->child[c-'a'];
        }
        return true;
    }
};

Trie (Prefiks Ağacı) Leetcode Java Həllini tətbiq edin:

class TrieNode {
    public char val;
    public boolean end;
    public TrieNode[] child = new TrieNode[26];
    public TrieNode() {}
    TrieNode(char c){
        TrieNode node = new TrieNode();
        node.val = c;
    }
}
public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }
    public void insert(String word) {
        TrieNode curr = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(curr.child[c - 'a'] == null){
                curr.child[c - 'a'] = new TrieNode(c);
            }
            curr = curr.child[c - 'a'];
        }
        curr.end = true;
    }
    public boolean search(String word) {
        TrieNode curr = root; 
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(curr.child[c - 'a'] == null) return false;
            curr = curr.child[c - 'a'];
        }
        return curr.end;
    }
    public boolean startsWith(String prefix) {
        TrieNode curr = root; 
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(curr.child[c - 'a'] == null) return false;
            curr = curr.child[c - 'a'];
        }
        return true;
    }
}

Trie (Prefiks Ağacı) Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N * L) burada N axtarış, daxil etmək üçün edilən və funksiya ilə başlayan zənglərin ümumi sayıdır, L isə parametr sətirinin maksimum uzunluğudur.

Yuxarıdakı kodun kosmik mürəkkəbliyi O(N*L). Bu trie məlumat strukturunda olan qovşaqları saxlamaq üçün istifadə olunan ümumi yerdir.