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.
This is my c++ solution...not sure why people balk at rolling their own trie data struct in c++
//simple trie data structclassPrefixTrie{public:unordered_map<char,PrefixTrie*>children;};voidnoPrefix(vector<string>words){PrefixTrieroot;//track if we are creating a new branchboolonNewBranch=true;for(stringw:words){PrefixTrie*next=&root;//add the word to the trie//if we encounter a node with no children then that means//we have seen the word before and its a prefix so bad set//also, if we add the entire word and never got to a new branch//then its a prefix of a word already in the treefor(charc:w){//if the node has children then its not a word we have seen if(next->children.empty()&&!onNewBranch){cout<<"BAD SET\n"<<w<<"\n";return;}//if the character doesnt exist in the children//then we are making a new branchif(next->children.find(c)==next->children.end()){next->children[c]=newPrefixTrie();onNewBranch=true;}next=next->children[c];}//if we got here but didnt make our own branch then we //are part of another word'd branch and therefor a prefixif(!onNewBranch){cout<<"BAD SET\n"<<w<<"\n";return;}onNewBranch=false;}cout<<"GOOD SET\n";}
No Prefix Set
You are viewing a single comment's thread. Return to all comments →
This is my c++ solution...not sure why people balk at rolling their own trie data struct in c++