algoadvance

Leetcode 1961. Check If String Is a Prefix of Array

Problem Statement

Given a string s and an array of strings words, determine if s is a prefix string of words. A string s is a prefix string of words if s can be formed by concatenating the first k strings in words for some positive k no larger than words.length.

If s is a prefix string of words, return true, otherwise return false.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be formed by concatenating "i", "love", and "leetcode".

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to form "iloveleetcode" by concatenating some of the first `k` strings in `words`.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the string s?
    • What is the maximum number of strings in the words array?
    • What is the maximum and minimum length of each string in the words array?
  2. Edge Cases:
    • What should be returned for an empty string s or an empty words array?
    • Should we consider cases where the concatenation of the initial k strings in words exceeds the length of s?

Strategy

The strategy to solve this problem can be described as follows:

  1. Initialize an empty string that will store the concatenation of strings from words.
  2. Iterate over the words array and keep appending each element to the concatenated string.
  3. After each concatenation, check if the resultant concatenated string equals s.
  4. If at any point the concatenated string becomes equal to s, return true.
  5. If the concatenated string becomes longer than s, break out of the loop since it is no longer possible to match s.
  6. If the loop completes without matching s, return false.

This strategy ensures that we are efficiently checking the prefix condition without unnecessary computations.

Time Complexity

The overall time complexity of the approach is O(n * m), where:

We now present the implementation in C++:

Code

#include <vector>
#include <string>

bool isPrefixString(std::string s, std::vector<std::string>& words) {
    std::string concatenated;
    for (const auto& word : words) {
        concatenated += word;
        if (concatenated == s) {
            return true;
        }
        if (concatenated.size() > s.size()) {
            return false;
        }
    }
    return false;
}

This implementation follows our outlined strategy:

  1. We maintain a concatenated string.
  2. Iterate through each word in words, and append it to concatenated.
  3. Check if concatenated matches s or exceeds its length.

By following this method, we efficiently determine if s is a prefix of the words array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI