Count Prefixes of a Given String - Solution & Explanation
Problem Statement
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]andsconsist of lowercase English letters only.
Approach Overview
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 1: Simple Iteration and Comparison
This approach involves iterating through each word in the array and checking if it is a prefix of the string s. A word is considered a prefix of s if the initial portion of s with the length of the word matches the word itself. For each word, extract the substring from s equating to the length of the word and compare the two.
This C program defines a function countPrefixes that iterates over each word in the words array, checking if it matches the beginning of string s using strncmp. If a match is found, it increments the count. Finally, it returns the total count of prefix matches.
Complexity
Time Complexity: O(n * k), where n is the number of words, and k is the maximum length of a word.
Space Complexity: O(1), no additional space is used apart from input storage.
Approach 2: Using Trie Data Structure to Optimize Prefix Checking
A more advanced approach employs a Trie (prefix tree) to efficiently check prefix relations. By inserting all possible prefixes of the string s into a Trie, you can then quickly check if each word is a prefix by verifying its existence in the Trie.
This C++ implementation uses a Trie structure to insert all prefixes of s. Each word in words is checked in the Trie to determine if it can be found starting from the root.
Complexity
Time Complexity: O(m + n * k), where m is the length of string s for prefix building in Trie and n * k is for checking each word against the Trie.
Space Complexity: O(m * 26), due to Trie node storage.
Approach 3: Traversal Counting
We directly traverse the array words, and for each string w, we check if s starts with w as a prefix. If it does, we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(m times n), where m and n are the lengths of the array words and the string s, respectively. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simple Iteration and Comparison | Time Complexity: O(n * k), where n is the number of words, and k is the maximum length of a word. |
| Using Trie Data Structure to Optimize Prefix Checking | Time Complexity: O(m + n * k), where m is the length of string s for prefix building in Trie and n * k is for checking each word against the Trie. |
| Traversal Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2255 Count Prefixes of a Given String | Zero to FAANG | Assignment Solution | Leetcode | Striver • Programmers Zone • 929 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Prefixes of a Given String easy or hard?
How to solve Count Prefixes of a Given String in O(n)?
Count Prefixes of a Given String Python or Java solution?
What is the best approach for Count Prefixes of a Given String?
What data structure is used in Count Prefixes of a Given String?
What is the time complexity of Count Prefixes of a Given String?
Is Count Prefixes of a Given String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Count Prefixes of a Given String with our built-in code editor and test cases.
Practice on FleetCode