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 problem was insane. It took me some time but I figured out how to satisfy the requirement to log the "first" (according to the input array's order) string that would trigger the prefix condition.
The optimal solution I found is to identify the first "BAD SET" case when inserting into the tree (since we're inserting in the order provided by the array).
Identifying prefixes after insertion into the trie has occured makes it difficult to ascertain which word or prefix was ordered first.
I added a returned boolean to the typical insertWord function that indicates whether there's an existing word in the Trie that is either:
* A prefix of the inserted word
* A duplicate of the inserted word
* Contains the inserted word (inserted word itself is a prefix)
classTrieNode{publicisWord:boolean;publicdata:string;publicchildren:Record<string,TrieNode>={};constructor(isWord:boolean,data:string){this.isWord=isWord;this.data=data;}}classPrefixTrie{privatetrie:TrieNode=newTrieNode(false,'');publicchildren:Record<string,TrieNode>={};/** * insertWord * @summary * Insert word in trie, return true or false depending on if prefix or duplicate word is found */insertWord(word:string):boolean{letprefixDetected=false;letcurr=this.trie;for(leti=0;i<word.length;i++){constchar=word[i];/** Case: curr node is prefix (i < word.length - 1) or duplicate of inserted word (i = word.length - 1) */if(curr.isWord){prefixDetected=true};if(!(charincurr.children)){constisWord=i===word.length-1;curr.children[char]=newTrieNode(isWord,word.substring(0,i+1))}elseif(i===word.length-1){/** Case: inserted word is prefix of another word (reached end of inserted word and curr has last char of inserted word in children) */prefixDetected=true;}curr=curr.children[char];}returnprefixDetected;}}/* * Complete the 'noPrefix' function below. * * The function accepts STRING_ARRAY words as parameter. * Time complexity: O(N * M), N = number of strings, M = average length of string * Space complexity: O(N * M), N = number of strings, M = average length of string */functionnoPrefix(words:string[]):void{letisGoodSet=true;constprefixTrieImpl=newPrefixTrie();letfailPointIndex:number|undefined=undefined;for(leti=0;i<words.length;i++){constprefixOrDuplicateFound=prefixTrieImpl.insertWord(words[i]);if(prefixOrDuplicateFound){console.log('BADSET');console.log(words[i]);return;}}console.log('GOODSET');}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
No Prefix Set
You are viewing a single comment's thread. Return to all comments →
This problem was insane. It took me some time but I figured out how to satisfy the requirement to log the "first" (according to the input array's order) string that would trigger the prefix condition.
The optimal solution I found is to identify the first "BAD SET" case when inserting into the tree (since we're inserting in the order provided by the array).
Identifying prefixes after insertion into the trie has occured makes it difficult to ascertain which word or prefix was ordered first.
I added a returned boolean to the typical
insertWord
function that indicates whether there's an existing word in the Trie that is either: * A prefix of the inserted word * A duplicate of the inserted word * Contains the inserted word (inserted word itself is a prefix)