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

标签: 数组 双指针 字符串

难度: Easy

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

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        sum = 0 
        for i in words:
            if sum == len(s):
                break
            if s[sum:sum+len(i)] == i:
                sum += len(i)
            else:
                return False
        if sum != len(s):return False 
        return True

Explain

该题解的思路是通过一个累加器 sum 来跟踪 s 中已匹配的字符数。对 words 数组中的每个字符串 i 进行遍历，首先检查当前 sum 是否已经等于 s 的长度，如果是，则停止处理，因为不需要再继续匹配更多的字符串。然后，检查 s 从位置 sum 到 sum + len(i) 的子串是否等于字符串 i。如果匹配，将 i 的长度加到 sum 上，继续下一个字符串的匹配；如果不匹配，直接返回 False。最后，循环结束后，检查 sum 是否等于 s 的总长度，如果是，则说明 s 可以完全由 words 数组中的一些字符串按顺序连接得到，否则返回 False。

时间复杂度: O(n * m)

空间复杂度: O(1)

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        sum = 0  # 累加器，用于跟踪 s 中已匹配的字符数
        for i in words:
            if sum == len(s):
                break  # 如果已匹配的长度等于 s 的长度，停止循环
            if s[sum:sum+len(i)] == i:
                sum += len(i)  # 如果当前单词匹配，增加 sum
            else:
                return False  # 如果当前单词不匹配，返回 False
        if sum != len(s):
            return False  # 如果最后的 sum 不等于 s 的长度，返回 False
        return True  # 所有条件满足，返回 True

Explore

该操作不会导致边界情况下的判断错误。当sum等于s的长度时，意味着s已被words数组中的前几个元素完全匹配，此时s的所有字符都已被正确组合，而后续的words元素是否继续存在已不影响结果。因此，提前终止循环是合理且高效的，避免了不必要的比较操作。

题解中的比较操作确实考虑到了这种情况。Python的字符串切片操作（s[sum:sum+len(i)]）在sum+len(i)超过s的长度时，会返回从sum开始到字符串结束的部分，而不会引发错误。如果这部分字符串不等于words中的字符串i，则会直接返回False，从而防止了索引超出范围的问题。

题解确实考虑了空字符串的存在。在Python中，空字符串的长度为0，因此在for循环中遇到空字符串时，sum的值不会增加。如果所有非空字符串已经使得sum等于s的长度，空字符串不会影响这一结果。因此，使用sum != len(s)来判断是有效的，它确保了所有必要的字符都已被匹配，且没有多余的字符。

在这个特定的问题中，使用for循环遍历words数组是一个直观且高效的方法，因为它直接按顺序检查words数组中的每个元素与s的匹配情况。递归或动态规划可能会引入不必要的复杂性和额外的内存使用。for循环方法在words数组相对短小，且每次比较操作代价不高时效率较高，特别是在需要顺序访问和处理每个元素的场景中。