Watch 10 video solutions for Check If String Is a Prefix of Array, a easy level problem involving Array, Two Pointers, String. This walkthrough by CodeClips with Abhishek Ranjan has 559 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |