跳转至

1961. 检查字符串是否为数组前缀

来源第 253 场周赛 Q1难度简单分数1234

题目描述

给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的 前缀字符串 。

字符串 s 要成为 words 的 前缀字符串 ，需要满足：s 可以由 words 中的前 k（k 为 正数 ）个字符串按顺序相连得到，且 k 不超过 words.length 。

如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。

 

示例 1：

输入：s = "iloveleetcode", words = ["i","love","leetcode","apples"]
输出：true
解释：
s 可以由 "i"、"love" 和 "leetcode" 相连得到。

示例 2：

输入：s = "iloveleetcode", words = ["apples","i","love","leetcode"]
输出：false
解释：
数组的前缀相连无法得到 s 。

 

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • 1 <= s.length <= 1000
  • words[i] 和 s 仅由小写英文字母组成

解法

方法一：遍历

思考

\(s\) 必须等于 \(\textit{words}\) 某个前缀的拼接，多一个或少一个词都不行。累加词长，长度首次等于 \(|s|\) 时比较拼接结果。

长度始终对不上则不是前缀字符串。不必在中途逐字符比对，一次拼接即可。

我们遍历数组 \(words\)，用一个变量 \(t\) 记录当前已经拼接的字符串，如果 \(t\) 的长度大于 \(s\) 的长度，说明 \(s\) 不是 \(words\) 的前缀字符串，返回 \(false\)；如果 \(t\) 的长度等于 \(s\) 的长度，返回 \(t\) 是否等于 \(s\)。

遍历结束后，如果 \(t\) 的长度小于 \(s\) 的长度，说明 \(s\) 不是 \(words\) 的前缀字符串，返回 \(false\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(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;
}

评论