1961. Check If String Is a Prefix of Array
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]
ands
consist of only lowercase English letters.
Solutions
Solution 1: Traversal
We traverse the array $words$, using a variable $t$ to record the currently concatenated string. If the length of $t$ is greater than the length of $s$, it means that $s$ is not a prefix string of $words$, so we return $false$; if the length of $t$ is equal to the length of $s$, we return whether $t$ is equal to $s$.
At the end of the traversal, if the length of $t$ is less than the length of $s$, it means that $s$ is not a prefix string of $words$, so we return $false$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|