Count Prefixes of a Given String

Easy

#2053Time: O(N * L), where `N` is the number of words in the `words` array and `L` is the maximum length of a word. For each of the `N` words, the `startsWith` check takes up to `O(L)` time.Space: O(1), as we only use a single integer variable for the counter, requiring constant extra space.

Data structures

Array String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each word in the input array words and checks if it is a prefix of the string s. A simple counter is used to keep track of the number of words that satisfy this condition.

Algorithm

1. Initialize an integer variable count to 0.
1. Iterate through each string in the words array.
1. For each string, check if s starts with it using the built-in s.startsWith(string) method.
1. If the check returns true, it means the current string is a prefix of s, so increment count.
1. After the loop finishes, return the final count.

Walkthrough

We initialize a counter variable, prefixCount, to zero. We then loop through every word in the words array. For each word, we can use the built-in startsWith() method of the String class to check if s begins with that word. The s.startsWith(word) method efficiently compares the characters of word with the beginning characters of s. If s.startsWith(word) returns true, it means word is a prefix of s, and we increment prefixCount. After checking all the words in the array, the final value of prefixCount is the answer. This method is straightforward to implement and understand, and given the problem's constraints, it is perfectly acceptable.

1class Solution {2    public int countPrefixes(String[] words, String s) {3        int count = 0;4        for (String word : words) {5            if (s.startsWith(word)) {6                count++;7            }8        }9        return count;10    }11}

Complexity

Time

O(N * L), where `N` is the number of words in the `words` array and `L` is the maximum length of a word. For each of the `N` words, the `startsWith` check takes up to `O(L)` time.

Space

O(1), as we only use a single integer variable for the counter, requiring constant extra space.

Trade-offs

Pros

Very simple to understand and implement.
Highly efficient in terms of space complexity.
For the given constraints, it's fast enough and might even outperform more complex solutions due to lower overhead.

Cons

Can be inefficient if the number of words (N) or the length of the words (L) is very large.
It repeatedly scans the beginning of string s for each word, which involves redundant comparisons if many words share common prefixes.

This approach uses a Trie (also known as a prefix tree) to optimize the process. First, all words from the words array are inserted into the Trie. Then, we traverse the string s on the Trie and sum up the counts of all words that form a prefix of s.

Algorithm

1. Define a TrieNode class with children (an array of 26 TrieNodes) and an integer count to track how many words end at this node.
1. Create a root TrieNode.
1. Build Phase: Iterate through each word in the words array.
1. For each word, traverse the Trie from the root, character by character, creating new nodes if they don't exist.
1. At the node corresponding to the last character of the word, increment its count.
1. Counting Phase: Initialize totalCount to 0 and a currentNode to root.
1. Iterate through each character c of the string s.
1. Move currentNode to its child corresponding to c.
1. If the child node is null at any point, it means no more prefixes of s can be found, so break the loop.
1. Add the count of the currentNode to totalCount. This count represents the number of words that are identical to the current prefix of s.
1. After iterating through s, return totalCount.

Walkthrough

A Trie is a specialized tree data structure for storing strings, where each node represents a character and paths from the root represent prefixes. First, we define a TrieNode class. Each node contains an array of children (one for each letter of the alphabet) and a counter, say count, to store how many words from the input array end at this node. We build the Trie by iterating through each word in the words array and inserting it. The insertion process involves traversing the Trie from the root, creating new nodes as necessary for each character in the word. When we reach the end of a word, we increment the count at the final node. After building the Trie, we traverse the string s character by character, starting from the Trie's root. For each prefix of s (i.e., s.substring(0, i+1)), we check the corresponding node in the Trie. The count at this node tells us how many words in the original array are exactly equal to this prefix. We sum up these counts for all prefixes of s to get the total.

1class TrieNode {2    TrieNode[] children;3    int count; // Number of words ending at this node4 5    public TrieNode() {6        children = new TrieNode[26];7        count = 0;8    }9}10 11class Solution {12    public int countPrefixes(String[] words, String s) {13        TrieNode root = new TrieNode();14        // Build the Trie15        for (String word : words) {16            TrieNode curr = root;17            for (char c : word.toCharArray()) {18                if (curr.children[c - 'a'] == null) {19                    curr.children[c - 'a'] = new TrieNode();20                }21                curr = curr.children[c - 'a'];22            }23            curr.count++;24        }25 26        int totalPrefixes = 0;27        TrieNode curr = root;28        // Traverse s on the Trie and count prefixes29        for (char c : s.toCharArray()) {30            if (curr.children[c - 'a'] == null) {31                break; // No more prefixes of s exist in the Trie32            }33            curr = curr.children[c - 'a'];34            totalPrefixes += curr.count; // Add all words that are equal to the current prefix of s35        }36        return totalPrefixes;37    }38}

Complexity

Time

O(W + M), where `W` is the total number of characters in all words in the `words` array, and `M` is the length of `s`. Building the Trie takes `O(W)` time. Traversing `s` on the Trie takes `O(M)` time.

Space

O(W), where `W` is the total number of characters in all words in the `words` array. In the worst case, the Trie will have a distinct node for each character of each word (if there are no shared prefixes).

Trade-offs

Pros

Very efficient for problems with many prefix-based queries on the same set of words, as the build time is a one-time cost.
Avoids redundant comparisons by structuring the words in a prefix-based hierarchy.

Cons

Higher implementation complexity compared to the brute-force approach.
Consumes more memory due to the Trie data structure. For this specific problem with its small constraints and a single query, the space overhead might not be justified.

Solutions

Solution

1public class Solution {2    public int CountPrefixes(string[] words, string s) {3        return words.Count(w => s.StartsWith(w));4    }5}

1class Solution { public int countPrefixes ( String [] words , String s ) { int ans = 0 ; for ( String w : words ) { if ( s . startsWith ( w )) { ++ ans ; } } return ans ; } }

1class Solution { public: int countPrefixes ( vector < string >& words , string s ) { int ans = 0 ; for ( auto & w : words ) { ans += s . starts_with ( w ); } return ans ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem