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

🟢   🔖  数组 双指针 字符串  🔗 力扣 LeetCode

题目

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 ifs _is a prefix string of _words , or falseotherwise.

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.

题目大意

给你一个字符串 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 仅由小写英文字母组成

解题思路

1. 遍历字符串数组：
   • 使用变量 length 来记录当前已连接字符串的长度。
   • 遍历数组 words，逐步累加当前字符串的长度。
2. 检查是否满足条件：
   • 如果累加长度 length 等于字符串 s 的长度 n，我们需要验证 s 是否等于数组 words 的前 i+1 个字符串的连接结果。
     • 如果相等，返回 true，否则，返回 false。
   • 如果 length > n，直接返回 false，因为连接的部分已经超过 s。
3. 返回结果：
   • 如果遍历完整个数组都未找到符合条件的前缀，则返回 false。

复杂度分析

• 时间复杂度：O(k + n)
  • 遍历 words 数组需要 O(k) 次，其中 k 是数组的长度。
  • 在每次检查时使用 join 拼接，最坏情况下字符串长度为 O(n)。
  • 总时间复杂度为 O(k + n)。
• 空间复杂度：O(n)，额外使用的空间主要来自 slice 和 join，最坏情况下需要 O(n) 的空间。

代码

/**
 * @param {string} s
 * @param {string[]} words
 * @return {boolean}
 */
var isPrefixString = function (s, words) {
	const n = s.length;
	let length = 0;
	for (let i = 0; i < words.length; i++) {
		length += words[i].length;
		if (length == n) {
			return s == words.slice(0, i + 1).join('');
		}
		if (length > n) {
			return false;
		}
	}
	return false;
};

相关题目

题号	标题	题解	标签	难度	力扣
2255	统计是给定字符串前缀的字符串数目	[✓]	数组 字符串	🟢	🀄️ 🔗