Scale Engineer

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
ArrayString

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:

  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.

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

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.

Solutions

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

Next problem