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 <= 1001 <= words[i].length <= 201 <= s.length <= 1000words[i]andsconsist of only lowercase English letters.
Solution: Concat and test
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: bool isPrefixString(string s, vector<string>& words) { string t; for (const string& w : words) { t += w; if (t.length() >= s.length()) break; } return t == s; } }; |