Easy

题目描述

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

字符串 s 是 words 的 前缀字符串，当且仅当 s 可以由 words 中的前 k（k 为 正数）个字符串按顺序相连得到。

如果 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
解释：
无法用 words 的前缀来构成 s。

提示：

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

解题思路

解题思路

这道题要求判断字符串 s 是否可以由数组 words 的前 k 个字符串按顺序拼接而成。

核心思路：

  1. 从 words 数组的第一个元素开始，依次拼接字符串
  2. 每次拼接后检查当前拼接结果是否与目标字符串 s 匹配
  3. 如果某次拼接后的长度超过了 s 的长度，或者内容不匹配，则返回 false
  4. 如果拼接结果恰好等于 s，则返回 true

算法步骤：

  1. 初始化一个空字符串 prefix 用于存储拼接结果
  2. 遍历 words 数组，逐个拼接字符串到 prefix
  3. 每次拼接后，检查 prefix 是否为 s 的前缀
  4. 如果 prefix 长度超过 s，或者不是 s 的前缀，返回 false
  5. 如果 prefix 等于 s，返回 true
  6. 如果遍历完所有单词都没有找到匹配，返回 false

时间复杂度为 O(n)，其中 n 是字符串 s 的长度，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string prefix = "";
        for (const string& word : words) {
            prefix += word;
            if (prefix.length() > s.length()) {
                return false;
            }
            if (prefix == s) {
                return true;
            }
            if (s.substr(0, prefix.length()) != prefix) {
                return false;
            }
        }
        return false;
    }
};

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        prefix = ""
        for word in words:
            prefix += word
            if len(prefix) > len(s):
                return False
            if prefix == s:
                return True
            if not s.startswith(prefix):
                return False
        return False

public class Solution {
    public bool IsPrefixString(string s, string[] words) {
        string prefix = "";
        foreach (string word in words) {
            prefix += word;
            if (prefix.Length > s.Length) {
                return false;
            }
            if (prefix == s) {
                return true;
            }
            if (!s.StartsWith(prefix)) {
                return false;
            }
        }
        return false;
    }
}

/**
 * @param {string} s
 * @param {string[]} words
 * @return {boolean}
 */
var isPrefixString = function(s, words) {
    let concat = "";
    for (let i = 0; i < words.length; i++) {
        concat += words[i];
        if (concat === s) {
            return true;
        }
        if (concat.length > s.length) {
            return false;
        }
    }
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为字符串 s 的长度，最多需要遍历一遍 s
空间复杂度O(n)需要额外空间存储拼接的前缀字符串

相关题目