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.
- No Prefix Set
- Discussions
No Prefix Set
No Prefix Set
+ 0 comments It can be solved with a custom trie.
class Trie { public: bool insert(string word) { if (!head) { head.reset(make_node(L'\0')); } bool foundPrefix = true; auto working = head.get(); for (auto c : word) { const auto idx = c - 'a'; if (working->isLeaf) { // hit a prefix trying to insert the word return true; } if (!working->children[idx]) { // we are appending to the trie, so no prefix was found. working->children[idx].reset(make_node(c)); foundPrefix = false; } working = working->children[idx].get(); } if (working) { working->isLeaf = true; } return foundPrefix; } private: struct Node { char data; std::unique_ptr<Node> children[10]; bool isLeaf; }; Node* make_node(char d) { return new Node{ d, {}, false }; } std::unique_ptr<Node> head{}; }; void noPrefix(vector<string> words) { Trie t; for (auto word : words) { if (t.insert(word)) { printf("BAD SET\n"); printf("%s\n", word.c_str()); return; } } printf("GOOD SET\n"); }
+ 0 comments I am here to let you know that this program is taking my soul out of my body mean for some input the expected output is too weird how can the first prefic they found is in posititon 12 or 16
+ 0 comments
As other users already pointed out, the problem description on what means "first checked" is confusing.
The tests effectively "define" first checked as the first word, which is either a:
- a) prefix of a previously seen word, or
- b) prefixed by a previously seen word
+ 0 comments My solution in Python 3 using trie
# Node of a prefix tree class Node: def __init__(self): self.children = {} self.EndOfWord = False # Trie data structure class Trie: def __init__(self): ''' Initialize a prefix tree with a root node. ''' self.root = Node() def insert(self, word: str) -> bool: ''' Insert a word into the prefix tree. Return True if any existing word is a prefix of currently inserted word. Else, return False. ''' current = self.root flag = False for c in word: if c not in current.children: current.children[c] = Node() current = current.children[c] if current.EndOfWord and not flag: flag = True current.EndOfWord = True return flag def startswith(self, prefix:str) -> bool: ''' Does the prefix tree contain entries starting with a specific prefix? ''' current = self.root for c in prefix: if c not in current.children: return False current = current.children[c] return True def noPrefix(words: list[str]) -> None: ''' Say N = len(words) and L = max word length. Space complexity: O(NL) Time complexity: O(NL) ''' # Write your code here trie = Trie() for word in words: # Check if word exists in trie. If not, add word to trie. if trie.startswith(word): print('BAD SET', word, sep='\n') return None # When inserting word into trie, determine if any pre-added word in trie is a prefix of the newly added word. bool_flag = trie.insert(word) if bool_flag: print('BAD SET', word, sep='\n') return None print('GOOD SET')
+ 0 comments This is my c++ solution...not sure why people balk at rolling their own trie data struct in c++
//simple trie data struct class PrefixTrie { public: unordered_map<char, PrefixTrie*> children; }; void noPrefix(vector<string> words) { PrefixTrie root; //track if we are creating a new branch bool onNewBranch = true; for(string w : 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 tree for(char c : 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 branch if(next->children.find(c) == next->children.end()) { next->children[c] = new PrefixTrie(); 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 prefix if(!onNewBranch) { cout << "BAD SET\n" << w << "\n"; return; } onNewBranch = false; } cout << "GOOD SET\n"; }
Load more conversations
Sort 146 Discussions, By:
Please Login in order to post a comment