Count Words Beginning with Prefix — Trie Count
Sanjeev SharmaAdvertisement
Problem
Return the number of strings in words that have pref as a prefix.
Solutions
Python — One-liner
class Solution:
def prefixCount(self, words: list[str], pref: str) -> int:
return sum(w.startswith(pref) for w in words)
Python — Trie
class Solution:
def prefixCount(self, words: list[str], pref: str) -> int:
root={}
for w in words:
node=root
for c in w:
if c not in node: node[c]={'cnt':0}
node=node[c]; node['cnt']+=1
node=root
for c in pref:
if c not in node: return 0
node=node[c]
return node['cnt']
Complexity
- Time: O(n * L) build, O(L) query | Space: O(n * L)
Advertisement
