1961

1961. Check If String Is a Prefix of Array (Easy)

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.

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/check-if-string-is-a-prefix-of-array/
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    bool isPrefixString(string s, vector<string>& A) {
        int j = 0, N = A.size();
        for (int i = 0; i < N && j < s.size(); ++i) {
            int k = 0;
            for (; j < s.size() && k < A[i].size() && s[j] == A[i][k]; ++k, ++j); // try matching `s` with `A[i]`.
            if (k != A[i].size()) return false; // If we can't match the entire `A[i]`, return false
        }
        return j == s.size(); // `s` must be matched entirely
    }
};