Given a string s and an array of strings words, determine whether s is a prefix string of words.
A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.
Return true if s is a prefix string of words, or false otherwise.
Example 1:
Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"] Output: true Explanation: s can be made by concatenating "i", "love", and "leetcode" together.
Example 2:
Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"] Output: false Explanation: It is impossible to make s using a prefix of arr.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 201 <= s.length <= 1000words[i] and s consist of only lowercase English letters.Problem Overview: You receive a string s and an array of strings words. The task is to check whether s equals the prefix formed by concatenating the first few elements of words. Concatenation must start from index 0 and stop once the built string either matches s or exceeds it.
Approach 1: Iterative Concatenation (O(n) time, O(n) space)
Build a running string by concatenating elements from words one by one. After each append, compare the built string with s. If it equals s, return true. If the length exceeds s, the prefix cannot match, so return false. The algorithm scans each character once overall, giving O(n) time where n is the total number of characters processed. The extra space comes from storing the temporary concatenated string.
This approach is straightforward and easy to reason about. It mirrors the definition of the problem: build the prefix and check if it matches. However, repeated string concatenation can allocate new memory depending on the language runtime.
Approach 2: Prefix Matching With Removal (O(n) time, O(1) space)
Instead of building a new string, match characters directly from s while iterating through words. Maintain an index pointer inside s. For each word, compare its characters with the corresponding characters in s. If a mismatch occurs, return false. If the pointer reaches the end of s exactly after processing part or all of a word, return true.
This method avoids creating intermediate strings and processes characters in-place. The pointer effectively simulates removing matched prefixes from s. Each character is visited once, resulting in O(n) time and O(1) extra space.
This approach resembles a typical pointer traversal pattern used in two pointers problems. You iterate through the array of words while scanning the string sequentially.
Recommended for interviews: Prefix Matching With Removal is usually preferred. It demonstrates careful pointer control and avoids unnecessary allocations. Iterative concatenation still shows correct reasoning and is perfectly acceptable for an easy problem, but interviewers generally expect the constant-space pointer-based solution.
This approach involves iteratively concatenating the words in the array and checking if at any point this concatenated string equals the given string s or becomes a prefix of it. Keep concatenating until the concatenated string size becomes larger than s, at which point you conclude that s cannot be constructed from these prefixes.
The C solution uses a character array to store the concatenated words. It iterates through the words and concatenates them one by one. After each concatenation, it checks if the resulting string equals s or has exceeded the length of s. The function returns true if it matches or false otherwise.
Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(mn) for storing the concatenated string.
This alternative approach involves checking prefixes of s using each word, iteratively removing the matching prefix from s. Continue until either s becomes empty (indicating a full match) or a non-matching word is encountered. This method directly compares sections of s with each word.
This C solution checks each word as a potential prefix of s by using strncmp. The index tracks how much of s has matched so far. If a full match occurs, it returns true; otherwise, false when mismatch happens.
Time Complexity: O(n * m) where n is the number of words and m is the average length of each word.
Space Complexity: O(1) as it uses constant extra space.
We traverse the array words, using a variable t to record the currently concatenated string. If the length of t is greater than the length of s, it means that s is not a prefix string of words, so we return false; if the length of t is equal to the length of s, we return whether t is equal to s.
At the end of the traversal, if the length of t is less than the length of s, it means that s is not a prefix string of words, so we return false.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Concatenation | Time Complexity: |
| Prefix Matching With Removal | Time Complexity: |
| Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Concatenation | O(n) | O(n) | Simple implementation when memory overhead from building strings is acceptable |
| Prefix Matching With Removal | O(n) | O(1) | Preferred solution when you want optimal space and direct character comparison |
Check If String Is a Prefix of Array| LeetCode 1961| English • CodeClips with Abhishek Ranjan • 559 views views
Watch 9 more video solutions →Practice Check If String Is a Prefix of Array with our built-in code editor and test cases.
Practice on FleetCode