LeetCode 1961 - Check If String Is a Prefix of Array

The problem is asking us to determine whether a given string s can be formed by concatenating the first k elements of an array words, where k is some positive integer less than or equal to the length of words.

leetcodeeasyarraytwo-pointersstring

LeetCode Problem 1961

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, String

Solution

Problem Understanding

The problem is asking us to determine whether a given string s can be formed by concatenating the first k elements of an array words, where k is some positive integer less than or equal to the length of words. In other words, s must match exactly the prefix of the array when all its strings are concatenated in order.

The input consists of a string s and a list of strings words. The expected output is a boolean value: true if s can be formed by concatenating a prefix of words and false otherwise. The constraints indicate that words is relatively small (up to 100 elements) and each string within it is short (up to 20 characters), while s can be longer (up to 1000 characters). Therefore, efficiency is important but we do not need extreme optimizations like advanced string matching algorithms.

Important edge cases include when s is shorter than the first element in words, when s equals a single word in words, when s is exactly the concatenation of all words in words, and when words contains elements that partially match s but cannot form a full prefix.

Approaches

A brute-force approach would concatenate every prefix of words incrementally and check if the resulting string matches s. This works because it directly simulates the definition of a prefix string. However, this can be inefficient, especially if the concatenated prefix grows larger than s, as unnecessary concatenation may occur.

The key insight for an optimal solution is that we do not need to build the entire concatenated string at once. Instead, we can iterate through words while keeping track of our position in s. For each word, we check if it matches the corresponding substring in s. If at any point a word does not match, we can immediately return false. This avoids unnecessary concatenations and allows for early termination.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n * m) Concatenate prefixes and compare with s directly. n = length of words, m = length of s.
Optimal O(m) O(1) Iterate through words and match substrings of s without creating a new string.

Algorithm Walkthrough

  1. Initialize a variable pos to 0 to track our current position in string s.
  2. Iterate through each word in words.
  3. For each word, check if the substring of s starting at pos and with length equal to the word matches the word.
  4. If it does not match, return false immediately.
  5. If it matches, increment pos by the length of the current word.
  6. After each increment, check if pos equals the length of s. If it does, we have matched the full string s using a prefix of words and can return true.
  7. If the loop completes without returning, s is longer than the concatenated prefix of words, so return false.

Why it works: The algorithm maintains the invariant that s[:pos] equals the concatenation of the first few words processed. If any word fails to match its corresponding substring in s, we can immediately conclude s is not a prefix string. This ensures correctness while avoiding unnecessary concatenation.

Python Solution

from typing import List

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        pos = 0
        for word in words:
            if pos + len(word) > len(s) or s[pos:pos + len(word)] != word:
                return False
            pos += len(word)
            if pos == len(s):
                return True
        return False

The code initializes a pos pointer to track the progress in s. For each word in words, it checks if the substring of s starting at pos matches the word. If not, it returns false. After adding the length of the word to pos, it checks if pos has reached the end of s, in which case the prefix is successfully matched. If the loop finishes without matching s completely, it returns false.

Go Solution

func isPrefixString(s string, words []string) bool {
    pos := 0
    for _, word := range words {
        if pos+len(word) > len(s) || s[pos:pos+len(word)] != word {
            return false
        }
        pos += len(word)
        if pos == len(s) {
            return true
        }
    }
    return false
}

The Go solution mirrors the Python logic. It uses pos to track the current index in s. The key differences are Go’s slice syntax s[pos:pos+len(word)] for substring extraction and explicit use of len() for lengths. No additional memory is allocated beyond integer tracking.

Worked Examples

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

Step word s[pos:pos+len(word)] pos Action
1 "i" "i" 0 -> 1 Match, increment pos
2 "love" "love" 1 -> 5 Match, increment pos
3 "leetcode" "leetcode" 5 -> 13 Match, pos equals len(s) -> return true

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

Step word s[pos:pos+len(word)] pos Action
1 "apples" "ilove" 0 -> 6 Mismatch -> return false

Complexity Analysis

Measure Complexity Explanation
Time O(m) Each character in s is checked at most once against words.
Space O(1) No extra data structures are used; only a pointer is maintained.

The time complexity is linear in the length of s because each character is examined at most once. The space complexity is constant since no additional arrays or concatenated strings are created.

Test Cases

# Basic examples
assert Solution().isPrefixString("iloveleetcode", ["i","love","leetcode","apples"]) == True  # exact prefix
assert Solution().isPrefixString("iloveleetcode", ["apples","i","love","leetcode"]) == False  # wrong start

# Edge cases
assert Solution().isPrefixString("a", ["a"]) == True  # single character match
assert Solution().isPrefixString("a", ["b"]) == False  # single character mismatch
assert Solution().isPrefixString("abc", ["a","b","c"]) == True  # multiple words exact match
assert Solution().isPrefixString("abc", ["a","b"]) == False  # prefix too short

# Longer s
assert Solution().isPrefixString("leetcode", ["leet","code"]) == True
assert Solution().isPrefixString("leetcode", ["leet","coder"]) == False
Test Why
"iloveleetcode" with correct prefix Validates basic matching logic
"iloveleetcode" with wrong first word Validates early termination on mismatch
Single character match Tests minimal input edge case
Single character mismatch Confirms mismatch handling
Multiple words exact match Confirms handling multiple concatenations
Prefix too short Confirms detection of incomplete prefix
Longer s with exact match Tests standard non-trivial concatenation
Longer s with last word mismatch Ensures algorithm stops correctly on mismatch

Edge Cases

One important edge case is when s is shorter than the first word in words. A naive implementation that attempts to concatenate or slice without bounds checking could crash or produce incorrect results. Our implementation explicitly checks pos + len(word) > len(s) before comparing.

Another edge case is when s is exactly the concatenation of all words in words. The algorithm handles this because pos will increment to match len(s) on the last word, and True will be returned correctly.

A third edge case is when words contains elements that partially match s but cannot fully construct it. For instance, s = "abcde" and words = ["ab", "cd", "f"]. The algorithm correctly identifies the mismatch at "f" and returns False immediately, preventing an incorrect match.