Problem Description

You are given a string s and an array of strings words. You need to determine if s can be formed by concatenating some consecutive strings from the beginning of the words array.

A string s is called a prefix string of words if you can take the first k strings from words (where k is at least 1 and at most the length of words), concatenate them together in order, and get exactly s.

For example:

• If words = ["a", "b", "c"] and s = "ab", then s is a prefix string because "a" + "b" = "ab"
• If words = ["a", "b", "c"] and s = "ac", then s is NOT a prefix string because you cannot form "ac" by concatenating consecutive strings from the beginning

The solution works by iterating through the words array and keeping track of the total length of concatenated strings using variable m. For each word, it adds the word's length to m. When m equals the length of s, it checks if concatenating all words up to the current index equals s. If they match, it returns true. If the loop completes without finding a match, it returns false.

The key insight is that we only need to check for equality when the accumulated length exactly matches the target string's length, avoiding unnecessary string concatenations at every step.

Intuition

The key observation is that if s is a prefix string, it must be formed by concatenating exactly the first k strings from words for some value of k. This means we need to find a point where the concatenation of words exactly matches s.

Instead of concatenating strings at each step (which would be inefficient), we can track the cumulative length of words as we iterate through the array. Why? Because if s has length n, and we've processed words with a total length of m:

• If m < n, we haven't concatenated enough words yet
• If m > n, we've gone too far and s cannot be a prefix string
• If m == n, this is the only point where we need to check if the concatenation equals s

This length-based approach saves us from performing expensive string concatenations at every iteration. We only build the concatenated string once - when the lengths match perfectly.

Think of it like filling a glass of water: you don't need to check if the glass is full after every drop. You only need to check when the water level reaches the rim. Similarly, we only need to verify the actual string content when the accumulated length matches our target length.

If we finish iterating through all words without ever hitting the exact length of s, then s cannot be formed by any prefix of words, so we return false.

Learn more about Two Pointers patterns.

Solution Approach

The implementation uses a traversal approach with length tracking to efficiently determine if s is a prefix string.

Algorithm Steps:

1. Initialize variables: We start with n = len(s) to store the target length, and m = 0 to track the cumulative length of words processed so far.

2. Iterate through words: We use enumerate(words) to traverse the array while keeping track of both the index i and the current word w.

3. Accumulate lengths: For each word w, we add its length to m using m += len(w). This gives us the total length of all words concatenated up to the current position.

4. Check for exact match: When m == n (cumulative length equals target length), we perform the actual string comparison:

   • We concatenate the first i + 1 words using "".join(words[:i + 1])
   • We compare this concatenation with s
   • If they match, we return true

5. Handle mismatches: If we complete the loop without finding a match (meaning either we never reached the exact length n, or we exceeded it), we return false.

Why this approach works:

• By tracking lengths first, we avoid unnecessary string operations until we find a potential match
• The condition m == n ensures we only check when we have exactly the right amount of characters
• If m exceeds n during iteration, the loop continues but will never satisfy m == n, eventually returning false
• The slicing operation words[:i + 1] gives us exactly the first i + 1 words needed for the prefix

Time Complexity: O(n) where n is the length of string s, as we potentially need to build and compare a string of length n.

Space Complexity: O(1) extra space if we don't count the space used for string concatenation in the comparison step.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm works step by step.

Example:

• words = ["cat", "dog", "fish"]
• s = "catdog"
• Target length n = 6

Step-by-step execution:

Iteration 1 (i=0, word="cat"):

• Current word: "cat" (length = 3)
• Update cumulative length: m = 0 + 3 = 3
• Check if m == n? → 3 == 6? No
• Continue to next word

Iteration 2 (i=1, word="dog"):

• Current word: "dog" (length = 3)
• Update cumulative length: m = 3 + 3 = 6
• Check if m == n? → 6 == 6? Yes!
• Now we perform the actual string check:
  • Concatenate first i+1 = 2 words: "cat" + "dog" = "catdog"
  • Compare with s: "catdog" == "catdog"? Yes!
• Return true

The algorithm successfully identifies that "catdog" can be formed by concatenating the first 2 words from the array.

Counter-example to show when it returns false:

Let's try with s = "catfi" (still length 6):

• Iteration 1: m = 3, not equal to 6, continue
• Iteration 2: m = 6, equals 6, check: "catdog" ≠ "catfi", continue
• Iteration 3: m = 10, exceeds 6, continue
• Loop completes without finding a match
• Return false

This demonstrates how the algorithm efficiently checks only when lengths match, avoiding unnecessary string operations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the words array and accumulates the total length m. In the worst case, it needs to check all words until m equals n (the length of string s). When m == n, it performs a string concatenation and comparison using "".join(words[:i+1]) == s. The join operation takes O(n) time since it concatenates strings with a total length of n characters, and the comparison also takes O(n) time. Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity comes from the string concatenation operation "".join(words[:i+1]). This creates a new string that, when m == n, has exactly n characters (same length as string s). The slicing operation words[:i+1] creates a new list reference but doesn't copy the string objects themselves. However, the join operation creates a new string of length n, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Early Termination When Length Exceeds Target

The Problem: In the provided code, there's an optimization attempt that returns False when current_length > target_length. However, this creates redundant code since the loop will naturally continue and never satisfy the current_length == target_length condition anyway.

Why It's Problematic:

• Adds unnecessary complexity to the code
• The early termination check if current_length > target_length: return False is redundant because once we exceed the target length, we'll never match it again
• Makes the code harder to read and maintain

Better Solution: Remove the redundant check and let the natural flow handle it:

def isPrefixString(self, s: str, words: List[str]) -> bool:
    target_length = len(s)
    current_length = 0
  
    for index, word in enumerate(words):
        current_length += len(word)
      
        if current_length == target_length:
            concatenated_string = "".join(words[:index + 1])
            return concatenated_string == s
  
    return False

Pitfall 2: Not Checking Character-by-Character Match

The Problem: The current solution only checks for string equality when lengths match, but it doesn't verify that the characters match as we go. This means we might do unnecessary iterations even when we already know the prefix doesn't match.

Example:

• s = "abc", words = ["x", "yz"]
• The algorithm will check length 1, skip comparison, then check length 3, but the first character already doesn't match

Better Solution: Check character matching as we build the prefix:

def isPrefixString(self, s: str, words: List[str]) -> bool:
    current_prefix = ""
  
    for word in words:
        current_prefix += word
      
        # If prefix is longer than s, it can't match
        if len(current_prefix) > len(s):
            return False
          
        # Check if current prefix matches the beginning of s
        if not s.startswith(current_prefix):
            return False
          
        # If we've built exactly s, we found a match
        if current_prefix == s:
            return True
  
    return False

Pitfall 3: Inefficient String Concatenation

The Problem: Using "".join(words[:index + 1]) creates a new list slice and then joins it every time we need to check. This is inefficient if we need to check multiple times or with large word arrays.

Better Solution: Build the string incrementally:

def isPrefixString(self, s: str, words: List[str]) -> bool:
    built_string = ""
  
    for word in words:
        built_string += word
      
        if len(built_string) == len(s):
            return built_string == s
        elif len(built_string) > len(s):
            return False
  
    return False

This approach avoids repeated slicing and joining operations, making it more efficient for larger inputs.