Skip to content

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] 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\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments