# Check If String Is a Prefix of Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-string-is-a-prefix-of-array)
Canonical: https://scaleengineer.com/dsa/problems/check-if-string-is-a-prefix-of-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
---
## Problem
Given a string `s` and an array of strings `words`, determine whether `s` is a **prefix string** of `words`.

A string `s` is a **prefix string** of `words` if `s` can be made by concatenating the first `k` strings in `words` for some **positive** `k` no larger than `words.length`.

Return `true` _if_ `s` _is a **prefix string** of_ `words`_, or_ `false` _otherwise_.

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

# Approaches
## Iterative Concatenation
This approach involves building a prefix string by concatenating words from the `words` array one by one. After each concatenation, we compare the resulting string with the target string `s`. This is an intuitive way to solve the problem as it directly simulates the process described in the problem statement.
**Time:** O(N * M), where N is the number of words and M is the length of `s`. In the worst case, for each of the `k` words that form a prefix, we create and compare a string of increasing length. The total work can be approximated as the sum of lengths of prefixes, which can be up to O(k * M). Since k can be at most N, the complexity is O(N * M). · **Space:** O(M), where M is the length of the string `s`. The `StringBuilder` will store characters up to a length comparable to `s`.
**Pros:** Intuitive and easy to understand.; Directly models the process described in the problem statement.
**Cons:** Less efficient in terms of time complexity due to repeated string creation (`toString()`) and comparisons within the loop.; Uses more memory to build the intermediate string.
### Explanation
We use a `StringBuilder` for efficient string concatenation. We iterate through the `words` array, appending each word to our `StringBuilder`. In each step of the iteration, we check two conditions:
1. If the length of our constructed string exceeds the length of `s`, it's impossible for it to be a prefix string, so we can stop and return `false`.
2. If the constructed string is exactly equal to `s`, we have found a match, and we can return `true`.

If we iterate through all the words and the constructed string never equals `s`, it means `s` is not a prefix string of `words`, so we return `false`.

```java
class Solution {
    public boolean isPrefixString(String s, String[] words) {
        StringBuilder prefixBuilder = new StringBuilder();
        for (String word : words) {
            prefixBuilder.append(word);
            if (prefixBuilder.toString().equals(s)) {
                return true;
            }
            if (prefixBuilder.length() > s.length()) {
                return false;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` called `prefixBuilder`.
- Iterate through each `word` in the `words` array.
- Append the current `word` to `prefixBuilder`.
- After appending, check if the length of `prefixBuilder` has exceeded the length of `s`. If so, it's impossible to form `s`, so we can immediately return `false`.
- Convert `prefixBuilder` to a string and compare it with `s`.
- If they are equal, it means `s` is a prefix string of `words`. Return `true`.
- If the loop completes without finding a match, it means no prefix of `words` concatenates to `s`. Return `false`.

## Optimal Pointer-based Comparison
A more efficient approach avoids building an intermediate string altogether. Instead, we can treat the `words` array as a single logical stream of characters and compare it directly with `s` using a pointer or an index. This avoids the overhead of creating new string objects in a loop.
**Time:** O(M), where M is the length of the string `s`. The `startsWith` check compares characters of `word` with characters of `s`. Each character of `s` is visited at most once across all calls. Therefore, the total time is proportional to the number of characters we successfully match, which is at most `M`. · **Space:** O(1). We only use a few variables to keep track of the index, requiring constant extra space.
**Pros:** Highly efficient in both time and space.; Avoids creating new string objects in a loop, which is a common performance bottleneck.; Processes each character of the target string `s` at most once.
**Cons:** May be slightly less direct to read for a beginner compared to the concatenation approach, though it's a standard pattern for string problems.
### Explanation
We maintain an index, `sIndex`, that tracks our current position in the target string `s`. We iterate through the `words` array. For each `word`, we check if the substring of `s` starting from `sIndex` matches the `word`. If at any point there is a mismatch, or if we exhaust the words before fully matching `s`, we know it's not a valid prefix string. If we perfectly match `s` after processing some `k`-th word, we've found our answer.

```java
class Solution {
    public boolean isPrefixString(String s, String[] words) {
        int sIndex = 0;
        for (String word : words) {
            // Check if we've already matched s or if the next word doesn't fit.
            if (sIndex >= s.length() || !s.startsWith(word, sIndex)) {
                return false;
            }
            
            // Move the index forward.
            sIndex += word.length();
            
            // If we have matched the entire string s, we are done.
            if (sIndex == s.length()) {
                return true;
            }
        }
        
        // The loop finished, but s was not fully matched.
        return false;
    }
}
```
### Algorithm
- Initialize an integer `sIndex = 0` to keep track of the matched portion of `s`.
- Iterate through each `word` in the `words` array.
- For each `word`, check if `s` starts with this `word` at the current `sIndex`. The `s.startsWith(word, sIndex)` method is ideal for this.
- If it does not match, `s` cannot be formed. Return `false`.
- If it does match, advance the `sIndex` by the length of the `word`.
- After advancing the index, check if `sIndex` is now equal to the length of `s`. If it is, we have successfully constructed `s`. Return `true`.
- If the loop finishes but we haven't returned `true`, it means the concatenated words from the array are a prefix of `s` but not equal to `s`. Return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPrefixString(String s, String[] words) {
    StringBuilder t = new StringBuilder();
    for (var w : words) {
      t.append(w);
      if (t.length() > s.length()) {
        return false;
      }
      if (t.length() == s.length()) {
        return s.equals(t.toString());
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPrefixString(string s, vector<string> &words) {
    string t;
    for (auto &w : words) {
      t += w;
      if (t.size() > s.size()) {
        return false;
      }
      if (t.size() == s.size()) {
        return t == s;
      }
    }
    return false;
  }
};

```

### Python

```python
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
```