2
\$\begingroup\$

Are there any suggestions about this?

#include <memory>
#include <unordered_map>
#include <vector>
#include <iostream>

using std::cout;
using std::endl;
using std::unordered_map;
using std::shared_ptr;
using std::make_shared;
using std::string;

struct TrieNode {
    bool isLeaf = false;
    unsigned int child_num = 0;
    unordered_map<char, shared_ptr<TrieNode>> children;
};

class Trie{
    shared_ptr<TrieNode> head;

    shared_ptr<TrieNode> atPrefix(const string& prefix) const {
        auto current = head;

        for (const char& letter : prefix) {
            auto next = current->children[letter];
            if (!next) return next;
            current = next;
        }
        return current;
    }

 public:
    Trie(void) : head(make_shared<TrieNode>()) {
        head->isLeaf = true;
        head->child_num = 0;
    }

    void insert(const string& word) const {
        auto current = head;
        for (const char& letter : word) {
            auto& next = current->children[letter];
            if (!next) next = make_shared<TrieNode>();
            next->child_num++;
            current = next;
        }
        current->isLeaf = true;
    }

    bool contains(const string& word) const {
        auto node = atPrefix(word);
        return node && node->isLeaf;
    }

    unsigned int wordsWithPrefix(const string& prefix) const {
        auto node = atPrefix(prefix);
        return node ? node->child_num : 0u;
    }
};

int main(int argc, char const *argv[]) {
    Trie trie;
    trie.insert("hello");
    cout << trie.contains("hello") << endl;
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.