周末没事，打一把力扣周赛，属于又菜又爱玩了。。当然这一题也没做出来，暴力解法超时了 这题有趣点在于用双指针求两个排序数组a、b，组满足abs(a[i] - b[j]) <= k 的集合

100207. 找出数组中的美丽下标 II

题目难度：hard

给你一个下标从 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 <= 5 * 105
  • 1 <= a.length, b.length <= 5 * 105
  • s、a、和 b 只包含小写英文字母。

解题思路：

  • 第一步用到了匹配字符串下标用到了KMP字符串匹配算法，求出两个匹配子串的起始位置数组a、b
  • 用双指针求两个排序数组a、b，组满足abs(a[i] - b[j]) <= k 的集合

总体时间复杂度：o(n)

代码：

class Solution {
    func beautifulIndices(_ s: String, _ a: String, _ b: String, _ k: Int) -> [Int] {
        var sArr = [Character](s)
        var aTarget = [Character](a)
        var bTarget = [Character](b)
        var posA = kmp(sArr, aTarget)
        var posB = kmp(sArr, bTarget)
        var res = [Int]()
        var j = 0
        var m = posB.count
        //双指针
        for i in posA {
            while j < m && i - posB[j] > k {
                j += 1
            }
            if j < m && abs(posB[j] - i) <= k {
                res.append(i)
            }
        }
        return res
    }

    func kmp(_ sArr: [Character], _ target: [Character] ) -> [Int] {
        var i = 0
        var j = 0
        var next = buildNext(target)
        var starts = [Int]()
        while i < sArr.count && j < target.count  {
            if sArr[i] == target[j] {
                i += 1
                j += 1
            } else if j > 0 {
                j = next[j - 1]
            } else {
                i += 1
            }
            if j == target.count {
                starts.append(i - j)
                j = next[j - 1]
            }
        }
        return starts
    }
    
    func buildNext(_ target: [Character]) -> [Int] {
        var next = [Int](repeating: 0, count: 1)
        var i = 1
        var prefix_len = 0
        while i < target.count {
            if target[prefix_len] == target[i] {
                prefix_len += 1
                next.append(prefix_len)
                i += 1
            } else {
                if prefix_len == 0 {
                    next.append(0)
                    i += 1
                } else {
                    prefix_len = next[prefix_len - 1]
                }
            }
        }
        return next
    }
    
}

KMP字符串匹配先不说了，网上有很多，后面有时间补上。

双指针代码解释：

        var res = [Int]()
        var j = 0
        var m = posB.count
        for i in posA {
            while j < m && i - posB[j] > k {
                j += 1
            }
            if j < m && abs(posB[j] - i) <= k {
                res.append(i)
            }
        }
        return res

因为数组 posA 和数组 posB都是有序并且递增的，可以想象在一条数轴上：

  • 1.如果 i > pos[j], && i - posB[j] > k 我们可以让 j 向数轴右侧移动让i - posB[j]缩短 ，这样可以淘汰一部分不必要要的计算
  • 2.如果 i < pos[j]
    • i 会一直增加，类似第一种情况的 j的递增，i也是在逼近posB[j] ，
    • 如果演变成 i > pos[j] 相当于又回到了第一种情况。

这段双指针代码的时间复杂度也是o(n)，所以这道题的整体时间复杂度也是o(n)