Watch 10 video solutions for Count Prefixes of a Given String, a easy level problem involving Array, String. This walkthrough by Programmers Zone has 919 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 10001 <= words[i].length, s.length <= 10words[i] and s consist of lowercase English letters only.Problem Overview: You receive a list of words and a target string s. The task is to count how many words in the array are prefixes of s. A word is a prefix if it matches the beginning portion of the string exactly.
The challenge is mostly about efficient string comparison. Since every candidate word must match the beginning of s, the solution focuses on checking prefix relationships without unnecessary work.
Approach 1: Simple Iteration and Comparison (O(n * m) time, O(1) space)
The most direct solution iterates through every word in the array. For each word, check whether it is a prefix of s. In most languages this is a single operation such as startsWith(), or you can manually compare characters until the word length is reached.
If the word length exceeds s, it cannot be a prefix, so skip it. Otherwise compare characters from index 0 to word.length - 1. Increment a counter whenever all characters match. The algorithm scans each word once, and the comparison takes up to the length of the word.
This results in O(n * m) time complexity where n is the number of words and m is the average word length. Space complexity stays O(1) because only a counter is maintained. For this problem's constraints, this solution is already optimal and extremely readable.
Approach 2: Using Trie Data Structure to Optimize Prefix Checking (O(n * m) build + O(m) traversal, O(n * m) space)
A more structured approach builds a Trie from the list of words. Each path in the Trie represents characters of a word, and terminal nodes mark completed words.
Once the Trie is built, traverse the target string s character by character. Each time you reach a node marked as a completed word, increment the prefix count. Stop traversal when the next character is not present in the Trie.
This approach works because every valid prefix must lie along the path defined by the characters of s. Trie traversal avoids repeatedly comparing characters across different words. The build phase costs O(n * m), and the traversal costs O(m). Space usage is O(n * m) for storing Trie nodes.
Recommended for interviews: The simple iteration solution is usually what interviewers expect first. It demonstrates clear reasoning about prefix checks and runs efficiently for typical constraints. Mentioning the Trie optimization shows deeper knowledge of prefix-based data structures and scalability for large dictionaries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iteration and Prefix Comparison | O(n * m) | O(1) | Best for most cases. Easy to implement and efficient for moderate input sizes. |
| Trie-Based Prefix Matching | O(n * m) build + O(m) query | O(n * m) | Useful when checking many prefix queries against the same dictionary. |