We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. No Prefix Set
  2. Discussions

No Prefix Set

  • ivanbilych
     + 0 comments

    C++11 variant with Trie. As it was pointed out tests want you to implement exactly this solution.

    class TrieNode {
    public:
        unordered_map<char, shared_ptr<TrieNode>> children;
        bool isEndOfWord;
        
        TrieNode() : isEndOfWord(false) {}
};

class Trie {
    public:
        Trie() : root(new TrieNode()) {}
        
        bool insert(string& word) {
            auto node = root;
            
            for (auto ch : word) {
                if (!node->children.count(ch)) {
                    node->children[ch] = shared_ptr<TrieNode>(new TrieNode());
                }
                
                node = node->children[ch];
                
                // Exit condition #1: This node is an end of some word
                if (node->isEndOfWord) {
                    return false;
                }
            }
            
            node->isEndOfWord = true;
            
            // Exit condition #2: This node is a prefix for some word
            if (!node->children.empty()) {
                return false;
            }
            
            return true;
        }
    
    private:
        shared_ptr<TrieNode> root;
};

void noPrefix(vector<string> words) {
    Trie trie;
    
    for (auto& word : words) {
        if (!trie.insert(word)) {
            cout << "BAD SET" << endl;
            cout << word << endl;
            return;
        }
    }
    
    cout << "GOOD SET" << endl;
}