Check If String Is a Prefix of Array

Easy

#1788Time: 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`.

Patterns

Two Pointers

Data structures

Array String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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.
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.

1class Solution {2    public boolean isPrefixString(String s, String[] words) {3        StringBuilder prefixBuilder = new StringBuilder();4        for (String word : words) {5            prefixBuilder.append(word);6            if (prefixBuilder.toString().equals(s)) {7                return true;8            }9            if (prefixBuilder.length() > s.length()) {10                return false;11            }12        }13        return false;14    }15}

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean isPrefixString(String s, String[] words) {3        int sIndex = 0;4        for (String word : words) {5            // Check if we've already matched s or if the next word doesn't fit.6            if (sIndex >= s.length() || !s.startsWith(word, sIndex)) {7                return false;8            }9            10            // Move the index forward.11            sIndex += word.length();12            13            // If we have matched the entire string s, we are done.14            if (sIndex == s.length()) {15                return true;16            }17        }18        19        // The loop finished, but s was not fully matched.20        return false;21    }22}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean isPrefixString(String s, String[] words) {4    StringBuilder t = new StringBuilder();5    for (var w : words) {6      t.append(w);7      if (t.length() > s.length()) {8        return false;9      }10      if (t.length() == s.length()) {11        return s.equals(t.toString());12      }13    }14    return false;15  }16}

1class Solution {2public:3  bool isPrefixString(string s, vector<string> &words) {4    string t;5    for (auto &w : words) {6      t += w;7      if (t.size() > s.size()) {8        return false;9      }10      if (t.size() == s.size()) {11        return t == s;12      }13    }14    return false;15  }16};

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem