Problem Statement
Brute Force [accepted]
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
res = 0
for word in words:
if word.startswith(pref):
res += 1
return res
Editorial
Approach 1: Brute Force
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
count = 0
for word in words:
count += self._has_prefix(word, pref)
return count
# Returns 1 if str has pref as prefix, 0 otherwise
def _has_prefix(self, str: str, pref: str) -> int:
itr = 0
# Compare characters until we reach the end of either string
while itr < len(str) and itr < len(pref):
if str[itr] != pref[itr]:
return 0 # Mismatch found
itr += 1
# Check if we've matched the entire prefix
if itr != len(pref):
return 0 # str is shorter than pref
return 1
Approach 2: Built-In Methods
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
return sum(word.startswith(pref) for word in words)
Approach 3: Trie
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
trie = self._Trie()
# Add all words to trie
for word in words:
trie._add_word(word)
return trie._count_prefix(pref)
class _Trie:
# Node class represents each character in Trie
class _Node:
def __init__(self):
# Links to child nodes
self.links = [None] * 26
# Number of strings having prefix till this node
self.count = 0
def __init__(self):
self.root = self._Node()
# Add word to trie and update prefix counts
def _add_word(self, word: str) -> None:
curr = self.root
for c in word:
idx = ord(c) - ord("a")
if curr.links[idx] is None:
curr.links[idx] = self._Node()
curr = curr.links[idx]
curr.count += 1 # Increment count for this prefix
# Return count of strings having pref as prefix
def _count_prefix(self, pref: str) -> int:
curr = self.root
for c in pref:
idx = ord(c) - ord("a")
if curr.links[idx] is None:
return 0 # Prefix not found
curr = curr.links[idx]
return curr.count # Return count at last node
