Check If String Is a Prefix of Array — Easy Problem & Solution

Problem statement

A string s is a prefix string of words if it equals the concatenation of the first k entries of words for some k with 1 <= k <= words.length.

Return true if s is a prefix string of words.

Example 1

Input: s = "codekairo", words = ["code","kairo","rocks"]
Output: true
Explanation: The first two words concatenate to exactly s.

Example 2

Input: s = "codek", words = ["code","kairo"]
Output: false
Explanation: One word gives "code" and two give "codekairo" — neither is "codek".

Example 3

Input: s = "a", words = ["a","b"]
Output: true

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• 1 <= s.length <= 1000
• All strings consist of lowercase English letters.

How to solve Check If String Is a Prefix of Array

There are only words.length candidate concatenations, and they grow monotonically, so build them one word at a time and test for equality after each addition.

Approach

1. Keep a growing buffer, initially empty.
2. Append each word in order; after each append compare the buffer with s.
3. Return true on an exact match; return false once the buffer is at least as long as s without matching.

Why it works

Every candidate is a prefix of the next, so lengths increase strictly. Once the buffer reaches s.length without matching, no later candidate can match either, which makes the early exit safe.

Complexity

• Time — O(n) where n is the total length of the words examined
• Space — O(n)

Pitfalls

• Using s.startsWith(buffer) tests the wrong direction — the statement asks for equality.
• Forgetting to stop makes the buffer grow past s and wastes work on a decided answer.

Reference solution

Python

from typing import List

def isPrefixString(s: str, words: List[str]) -> bool:
    built = ""
    for w in words:
        built += w
        if built == s:
            return True
        if len(built) >= len(s):
            return False
    return False

JavaScript

var isPrefixString = function(s, words) {
    var built = "";
    for (var i = 0; i < words.length; i++) {
        built += words[i];
        if (built === s) return true;
        if (built.length >= s.length) return false;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Find the Original Typed String I Easy
• Rearrange Characters to Make Target String Easy
• Number of Strings That Appear as Substrings in Word Easy
• Circular Sentence Easy
• Number of Senior Citizens Easy
• Find Words Containing Character Easy