找出数组中的美丽下标 I

标签: 双指针 字符串 二分查找 字符串匹配 哈希函数 滚动哈希

难度: Medium

给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。

如果下标 i 满足以下条件，则认为它是一个 美丽下标：

  • 0 <= i <= s.length - a.length
  • s[i..(i + a.length - 1)] == a
  • 存在下标 j 使得：
    • 0 <= j <= s.length - b.length
    • s[j..(j + b.length - 1)] == b
    • |j - i| <= k

以数组形式按 从小到大排序 返回美丽下标。

示例 1：

输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
输出：[16,33]
解释：存在 2 个美丽下标：[16,33]。
- 下标 16 是美丽下标，因为 s[16..17] == "my" ，且存在下标 4 ，满足 s[4..11] == "squirrel" 且 |16 - 4| <= 15 。
- 下标 33 是美丽下标，因为 s[33..34] == "my" ，且存在下标 18 ，满足 s[18..25] == "squirrel" 且 |33 - 18| <= 15 。
因此返回 [16,33] 作为结果。

示例 2：

输入：s = "abcd", a = "a", b = "a", k = 4
输出：[0]
解释：存在 1 个美丽下标：[0]。
- 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。
因此返回 [0] 作为结果。

提示：

  • 1 <= k <= s.length <= 105
  • 1 <= a.length, b.length <= 10
  • s、a、和 b 只包含小写英文字母。

Submission

运行时间: 70 ms

内存: 21.3 MB

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        lsta, lstb = [-1], [-1]
        while (i := s.find(a, lsta[-1] + 1)) != -1: lsta.append(i)
        while (i := s.find(b, lstb[-1] + 1)) != -1: lstb.append(i)
        ans, j, n = [], 1, len(lstb)
        for i in lsta[1:]:
            while j < n and lstb[j] < i - k: j += 1
            if j == n: break
            if lstb[j] <= i + k: ans.append(i)
        return ans

Explain

此题解首先使用两个列表分别存储字符串 s 中所有 a 和 b 的出现下标。使用字符串的 find 方法来找到所有出现的下标，存储在 lsta 和 lstb 中。之后，遍历 lsta 中的每一个下标 i，使用两个指针技术（一个指针遍历 lsta，另一个指针遍历 lstb），查找是否存在一个下标 j 在 lstb 中，使得 |j - i| <= k。如果找到这样的 j，则将 i 添加到结果列表中。最后返回结果列表。

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

空间复杂度: O(la + lb)

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        lsta, lstb = [-1], [-1]  # 初始化两个列表存储匹配字符串 a 和 b 的起始索引
        # 查找所有 a 的出现位置
        while (i := s.find(a, lsta[-1] + 1)) != -1: lsta.append(i)
        # 查找所有 b 的出现位置
        while (i := s.find(b, lstb[-1] + 1)) != -1: lstb.append(i)
        ans, j, n = [], 1, len(lstb)  # 初始化结果列表，双指针 j，和 lstb 的长度
        # 遍历所有 a 的匹配位置
        for i in lsta[1:]:
            while j < n and lstb[j] < i - k: j += 1  # 移动指针 j 直到找到满足条件的 b 的位置
            if j == n: break  # 如果 j 超出范围，则终止循环
            if lstb[j] <= i + k: ans.append(i)  # 如果找到满足条件的 j，则将当前的 i 加入结果列表
        return ans

Explore

在此题解中，选择使用find方法而不是更复杂的字符串搜索算法如KMP或Boyer-Moore，可能是因为find方法在Python标准库中已经实现，易于使用且足够高效。这些高级算法虽然在最坏情况下提供更优的时间复杂度，但实际编程中，直接使用内置的find方法可以减少代码复杂性和实现错误的风险。此外，除非处理的字符串极长或查找操作极为频繁，否则简单的方法往往在实际应用中已足够高效。

find方法通过从上一个找到的索引后一个位置开始搜索来确保不遗漏任何匹配位置。每次调用find时，都会指定新的起始位置为上一次找到的匹配位置加1。这样，每次搜索都会从上一个匹配的下一个字符开始，直到字符串末尾。这种方法确保了每个匹配都会被依次找到，不会有重叠或遗漏。

在lstb中索引0存储的是-1用于处理边界情况，确保即使字符串b在字符串s的开头位置就出现时，也能正确处理比较逻辑。将j初始化为1而不是0是因为索引0的值为-1并不代表一个有效的字符索引，而是一个初始的边界值。遍历lsta的每个索引i时，从lstb的1开始，确保比较的是有效的b字符出现的索引。这种做法避免了无效比较，并且有助于减少不必要的计算。