follow up question: what is "pref" is not just a word anymore, but, "pref" is array, and for each element in this array, we need to calculate a answer!! will you still use Brute-force!?? ask yourself, Does it make sense now, to use prefix-trie here??
#python optimal solution #Let n be the total number of strings in the input array words, l be the maximum length of any string in words, and m be the length of the prefix string pref. #tc= O(n⋅l+m) #sc=O(n⋅l) class Node: def __init__(self): self.nextChar={} self.prefixFreq=1 class Trie: def __init__(self): self.root=Node() self.root.prefixFreq=0 def insertWord(self,word): node=self.root for i in word: if(i not in node.nextChar): node.nextChar[i]=Node() else: node.nextChar[i].prefixFreq+=1 node=node.nextChar[i] def prefixFreq(self,prefixx): node=self.root #prefixFreq=0 for i in prefixx: if(i not in node.nextChar): return 0 else: node=node.nextChar[i] return node.prefixFreq
class Solution: def prefixCount(self, words: List[str], pref: str) -> int: trie=Trie() for word in words: if(word[0]==pref[0]): trie.insertWord(word)
//java MOST optimal solution
class Node{
Map nextChar;
int prefixFreq;
Node(){
nextChar=new HashMap();
prefixFreq=1;
}
}
class Trie{
Node root;
Trie(){
root=new Node();
root.prefixFreq=0;
}
public void insertWord(String word){
Node node=this.root;
for(int i=0;i
Incredible 🔥🔥🔥
Keep it up sir really Helpful for me 😊
Glad it helped you! 😊
English Explanation: th-cam.com/video/XpQjELkafLQ/w-d-xo.html
follow up question:
what is "pref" is not just a word anymore, but, "pref" is array, and for each element in this array, we need to calculate a answer!!
will you still use Brute-force!??
ask yourself, Does it make sense now, to use prefix-trie here??
#python optimal solution
#Let n be the total number of strings in the input array words, l be the maximum length of any string in words, and m be the length of the prefix string pref.
#tc= O(n⋅l+m)
#sc=O(n⋅l)
class Node:
def __init__(self):
self.nextChar={}
self.prefixFreq=1
class Trie:
def __init__(self):
self.root=Node()
self.root.prefixFreq=0
def insertWord(self,word):
node=self.root
for i in word:
if(i not in node.nextChar):
node.nextChar[i]=Node()
else:
node.nextChar[i].prefixFreq+=1
node=node.nextChar[i]
def prefixFreq(self,prefixx):
node=self.root
#prefixFreq=0
for i in prefixx:
if(i not in node.nextChar):
return 0
else:
node=node.nextChar[i]
return node.prefixFreq
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
trie=Trie()
for word in words:
if(word[0]==pref[0]):
trie.insertWord(word)
return trie.prefixFreq(pref)