#1961

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Check If String Is a Prefix of Array

Determine if a string is a prefix of an array by concatenating initial elements, using two-pointer scanning efficiently.

array two pointers string

Problem Statement

Given a string s and an array of strings words, determine whether s can be formed by concatenating the first k strings in words for some k between 1 and words.length. Return true if such a prefix exists, otherwise return false.

For example, given s = 'iloveleetcode' and words = ['i','love','leetcode','apples'], the prefix made by the first three words matches s exactly, so the output is true. If no combination of initial words forms s, the output must be false.

Examples

Example 1

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]

Output: true

s can be made by concatenating "i", "love", and "leetcode" together.

Example 2

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]

Output: false

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.

Solution Approach

Two-Pointer Incremental Match

Use one pointer for s and one for words. Scan characters of s against characters in consecutive words, advancing the word pointer after each word. Return false immediately if any mismatch occurs.

Concatenate Prefix On the Fly

Instead of joining all words at once, accumulate characters from words until either the length equals s or a mismatch happens. This avoids extra memory and keeps the check efficient.

Early Exit on Length Check

If the accumulated characters exceed the length of s, return false immediately. This prevents scanning unnecessary words and ensures linear time complexity tied to s and relevant prefix words.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(L) where L is the sum of lengths of the words used in the prefix, as we scan each character once. Space complexity is O(1) extra space if concatenation is done incrementally without building a full string.

What Interviewers Usually Probe

Checking two-pointer alignment between s and words array.
Observing early exit opportunities when prefix lengths mismatch.
Identifying incremental concatenation versus full array join.

Common Pitfalls or Variants

Common pitfalls

Attempting to join all words before comparing, which wastes memory and time.
Ignoring partial matches and scanning beyond necessary prefix length.
Mismanaging pointer increments when word boundaries are crossed.

Follow-up variants

Instead of string s, check if a sequence of numbers is a prefix of an array of arrays.
Allow s to match any subsequence of words rather than just a prefix.
Check prefix matching ignoring case sensitivity or including delimiters.

FAQ

What is the main approach for Check If String Is a Prefix of Array?

Use two-pointer scanning, advancing through s and words incrementally, and return false on the first mismatch.

Can I join all words first and compare?

Joining all words works but is inefficient; incremental scanning with two pointers reduces memory usage and time.

What happens if s is longer than the concatenation of all words?

The function immediately returns false, as no prefix can match a longer string.

Does order of words matter in matching s?

Yes, only the initial k words in order can form a valid prefix of s.

Is this pattern always suitable for large arrays?

Yes, as long as two-pointer scanning with early exits is used, it remains linear and memory-efficient.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        n, m = len(s), 0
        for i, w in enumerate(words):
            m += len(w)
            if m == n:
                return "".join(words[: i + 1]) == s
        return False

Continue Practicing

#1898 maximum number of removable characters #2108 find first palindromic string in the array #1813 sentence similarity iii