Check If String Is a Prefix of Array

EASY

Description

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

Checkout 2 different approaches to solve Check If String Is a Prefix of Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(M), where M is the length of the string `s`. The `StringBuilder` will store characters up to a length comparable to `s`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check If String Is a Prefix of Array. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Check If String Is a Prefix of Array

Patterns:

Two Pointers

Data Structures:

ArrayString