Skip to main content
Talentd

Check If String Is a Prefix of Array - Solution & Explanation

EasyArrayTwo PointersString15 min readAsked at: Uber
Practice this problem

Problem Statement

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 <= 100
  • 1 <= words[i].length <= 20
  • 1 <= s.length <= 1000
  • words[i] and s consist of only lowercase English letters.

Approach Overview

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 1: Iterative Concatenation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Prefix Matching With Removal

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Traversal

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Concatenation

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.

Prefix Matching With Removal

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.

Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative ConcatenationO(n)O(n)Simple implementation when memory overhead from building strings is acceptable
Prefix Matching With RemovalO(n)O(1)Preferred solution when you want optimal space and direct character comparison

Video Solution

Check If String Is a Prefix of Array| LeetCode 1961| English • CodeClips with Abhishek Ranjan • 567 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check If String Is a Prefix of Array easy or hard?
LeetCode classifies this problem as Easy. It mainly tests understanding of string traversal, array iteration, and careful pointer movement rather than advanced algorithms.
Check If String Is a Prefix of Array Python/Java solution
In Python or Java, iterate through the words array and compare characters of each word against the current index in s. Stop once s is fully matched or a mismatch occurs. The logic is identical across languages and runs in O(n) time.
How to solve Check If String Is a Prefix of Array in O(n)?
Use a pointer index for string s and iterate through the words array from the beginning. Compare each character of the current word with s[index]. Increment the index as matches occur. If the index reaches the length of s exactly, return true; if a mismatch occurs or words end early, return false.
What is the best approach for Check If String Is a Prefix of Array?
Prefix matching with a pointer over the target string is the best approach. Instead of concatenating all words, iterate through each word and compare characters directly with the string s. This processes each character once, giving O(n) time complexity and O(1) extra space.
Is Check If String Is a Prefix of Array asked at Google/Amazon/Meta?
This problem represents a common string and array traversal pattern often used in interviews at large tech companies. While the exact question may vary, similar prefix-checking or sequential matching problems appear in screening rounds at companies like Amazon and Google.
What data structure is used in Check If String Is a Prefix of Array?
The solution primarily uses arrays and strings with sequential traversal. No advanced data structures are required. The optimal method relies on pointer-style iteration, a common pattern in two pointers and string processing problems.
What is the time complexity of Check If String Is a Prefix of Array?
The optimal solution runs in O(n) time, where n is the total number of characters examined across s and the prefix portion of words. Each character is compared at most once. Space complexity can be O(1) if you avoid building intermediate strings.

Ready to solve this problem?

Practice Check If String Is a Prefix of Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Prefixes of a Given String