Teaching Kids Programming – Algorithms to Count Prefixes of a Given String (Trie Data Structure)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters. Return the number of strings in words that are a prefix of s. A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:
Input: words = [“a”,”b”,”c”,”ab”,”bc”,”abc”], s = “abc”
Output: 3
Explanation:
The strings in words which are a prefix of s = “abc” are:
“a”, “ab”, and “abc”.
Thus the number of strings in words which are a prefix of s is 3.

Example 2:
Input: words = [“a”,”a”], s = “aa”
Output: 2
Explanation:
Both of the strings are a prefix of s.
Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints:
1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i] and s consist of lowercase English letters only.

Hint:
For each string in words, check if it is a prefix of s. If true, increment the answer by 1.

Prefix Check Algorithm using startswith method

Python has inbuilt startswith method for a string, we can then iterate over the words in the list, and check if it is the prefix of the given string s.

1
2
3
4
5
6
7

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        ans = 0
        for w in words:
            if s.startswith(w):
                ans += 1
        return ans

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        ans = 0
        for w in words:
            if s.startswith(w):
                ans += 1
        return ans

We can use one-liner using list’s count method:

1

return [s.startswith(i) for i in words].count(True)

return [s.startswith(i) for i in words].count(True)

or via the map function:

1

return sum(map(s.startswith, words))

return sum(map(s.startswith, words))

Using Trie to Check Prefix

A Trie is a handy data structure that helps to find a prefix or string in a list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Trie:
    def __init__(self):
        self.data = {}
        self.counter = 0
 
    def insert(self, word: str) -> None:
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.counter += 1
 
    def search(self, word: str) -> bool:
        cur = self
        for i in word:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return cur.counter > 0
        
    def startsWith(self, prefix: str) -> bool:
        cur = self
        for i in prefix:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return True  
    
    def count(self, prefix: str) -> int:
        cur = self
        for i in prefix:
            if not i in cur.data:
                return 0
            cur = cur.data[i]
        return cur.counter      

class Trie:
    def __init__(self):
        self.data = {}
        self.counter = 0
 
    def insert(self, word: str) -> None:
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.counter += 1
 
    def search(self, word: str) -> bool:
        cur = self
        for i in word:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return cur.counter > 0
        
    def startsWith(self, prefix: str) -> bool:
        cur = self
        for i in prefix:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return True  
    
    def count(self, prefix: str) -> int:
        cur = self
        for i in prefix:
            if not i in cur.data:
                return 0
            cur = cur.data[i]
        return cur.counter      

Then, with a Trie, we can insert the string, and then the rest would be the same (replacing the string’s startswith method).

1
2
3
4
5

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        trie = Trie()
        trie.insert(s)
        return sum(map(trie.startsWith, words))

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        trie = Trie()
        trie.insert(s)
        return sum(map(trie.startsWith, words))

–EOF (The Ultimate Computing & Technology Blog) —