LeetCode 1961. Check If String Is a Prefix of Array Solution in Java, C++, Python & More | Explanation + Code

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] and s 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.

PythonJavaC++GoTypeScript

class Solution: def isPrefixString(self, s: str, words: List[str]) -> bool: n, m = len(s), 0 for i, w in enumerate(words): m += len(w) if m == n: return "".join(words[: i + 1]) == s return False(code-box)

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; } }(code-box)

class Solution { public: bool isPrefixString(string s, vector<string>& words) { string t; for (auto& w : words) { t += w; if (t.size() > s.size()) { return false; } if (t.size() == s.size()) { return t == s; } } return false; } };(code-box)

func isPrefixString(s string, words []string) bool { t := strings.Builder{} for _, w := range words { t.WriteString(w) if t.Len() > len(s) { return false } if t.Len() == len(s) { return t.String() == s } } return false }(code-box)

function isPrefixString(s: string, words: string[]): boolean { const t: string[] = []; const n = s.length; let m = 0; for (const w of words) { m += w.length; if (m > n) { return false; } t.push(w); if (m === n) { return s === t.join(''); } } return false; }(code-box)