Check If String Is a Prefix of Array

Difficulty: Easy | Acceptance: 52.80% | Paid: No Topics: Array, Two Pointers, String

Given a string s and an array of strings words, determine whether s is a prefix string of the concatenated string formed by words in order.

A prefix string is a string that can be made by concatenating some prefix of the array words (i.e., some contiguous subarray starting from the beginning).

• Examples
• Constraints
• Approach 1: Iterative Concatenation
• Approach 2: Two Pointers / Index Tracking

Examples

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 <= 10⁴
words[i] and s consist of only lowercase English letters.

Approach 1: Iterative Concatenation

Intuition We can simulate the process of building the prefix string by iterating through the words array and appending each word to a temporary string. After each append, we check if the temporary string matches s or if it has become longer than s.

Steps

• Initialize an empty string current to store the concatenated prefix.
• Iterate through each word in the words array.
• Append the current word to current.
• Check if current is equal to s. If yes, return true.
• Check if the length of current is greater than the length of s. If yes, return false because s cannot be a prefix of a string that is already longer than it.
• If the loop finishes without finding a match, return false.

class Solution:
    def isPrefixString(self, s: str, words: list[str]) -> bool:
        current = ""
        for word in words:
            current += word
            if current == s:
                return True
            if len(current) > len(s):
                return False
        return False

Complexity

• Time: O(N * L), where N is the number of words and L is the average length of a word. In the worst case, we construct a string of length equal to s.
• Space: O(N * L) to store the current string.
• Notes: This approach is intuitive but uses extra space to store the concatenated string.

Approach 2: Two Pointers / Index Tracking

Intuition Instead of building a new string, we can optimize space by tracking the current position (index) in s that we are trying to match. We iterate through the words and then through the characters of each word, comparing them with the corresponding character in s.

Steps

• Initialize a pointer k = 0 to track the current index in s.
• Iterate through each word in the words array.
• Iterate through each character in the current word.
• If k is equal to the length of s, it means we have successfully matched all characters of s previously, but we are still processing a word. This implies s is shorter than the current prefix, so return false.
• If the current character from the word does not match s[k], return false.
• Increment k to move to the next character in s.
• After finishing the inner loop (processing a word), check if k equals the length of s. If yes, we have matched s exactly at the end of a word, so return true.
• If the outer loop finishes, check if k equals the length of s (handles the case where s is empty, though constraints say min length 1) or simply return false if we exited without matching.

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

Complexity

• Time: O(S), where S is the length of s. We stop iterating as soon as we finish matching s or find a mismatch.
• Space: O(1), as we only use a few integer variables for pointers and do not allocate extra space proportional to the input size.
• Notes: This is the optimal approach as it minimizes space usage and avoids unnecessary string copying.