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.
- Prepare
- Data Structures
- Trie
- No Prefix Set
- Discussions
No Prefix Set
No Prefix Set
+ 0 comments Hi, I would like to know what's the expected output for this example:
2
ab
a
thanks!
+ 1 comment C++ Solution. Passed all the tests
class Trie{ public: Trie *childNodes[10]; int wordCount; Trie(){ for(int i=0;i<10;i++){ childNodes[i]=NULL; } wordCount = 0; } }; bool insert_key(Trie *root, string key_word){ Trie *currentNode = root; for(int i=0;i<key_word.size();i++){ int index = key_word[i]-'a'; if(currentNode->childNodes[index]==NULL){ Trie *newNode = new Trie(); currentNode->childNodes[index]= newNode; } else{ if(currentNode->childNodes[index]->wordCount || i==key_word.size()-1){ return false; } } currentNode = currentNode->childNodes[index]; } currentNode->wordCount++; return true; } void noPrefix(vector<string> words) { Trie *root = new Trie(); for(auto word : words){ if(!insert_key(root, word)){ cout<< "BAD SET \n"<< word; return; } } cout<<"GOOD SET "; }
+ 0 comments Completed by creating a tree representation of the word set.
class Tree: def __init__(self, words): self.words = words self.root = Node(None) self.checkForPrefix() def checkForPrefix(self): for word in words: answer = self.insert(word) if answer is not None: print("BAD SET") print(answer) return print("GOOD SET") def insert(self, word): current = self.root for i in range(len(word)): c = word[i] if current.branches[self.indexOf(c)] != None and i == len(word) - 1: return word if current.branches[self.indexOf(c)] == None: current.branches[self.indexOf(c)] = Node(c) if current.branches[self.indexOf(c)].isComplete: return word if i == len(word) - 1: current.branches[self.indexOf(c)].isComplete = True current = current.branches[self.indexOf(c)] return None def indexOf(self, c): return ord(c) - 97 class Node: def __init__(self, value): self.value = value self.isComplete = False self.branches = [None] * (ord("j") - ord("a") + 1) def noPrefix(words): # Write your code here root = Tree(words)
+ 0 comments No need to make this more complicated than it should be
def noPrefix(words): dic = {} for i in range(len(words)): start = dic for j in range(len(words[i])): if words[i][j] not in start: start[words[i][j]] = {} start = start[words[i][j]] if '*' in list(start.keys()) or (j == len(words[i]) - 1 and (start)): print("BAD SET\n", words[i], sep = '') return start['*'] = True print('GOOD SET')
+ 0 comments Regular expression is best to match pattern. If you want validation like checking the value / length of matched expression / subexpression, it is better to do that outside regex. Keep your regex as simple as possible, so you don’t waste computational time for something that can be done more efficiently outside regex. https://wordmaker.info/how-many/prefix.html
Load more conversations
Sort 152 Discussions, By:
Please Login in order to post a comment