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 <= 10^5
  • 1 <= a.length, b.length <= 10
  • s、a 和 b 只包含小写英文字母。

解题思路

这道题需要找到字符串中同时满足两个条件的索引：1) 该位置匹配字符串a，2) 在距离k范围内存在匹配字符串b的位置。

解题思路：

  1. 预处理阶段：首先找到所有匹配字符串a的索引位置和所有匹配字符串b的索引位置。可以使用字符串匹配算法如KMP，或者直接使用substring比较。

  2. 双指针优化：对于每个匹配a的索引i，需要检查是否存在匹配b的索引j满足|i-j|≤k。朴素方法是对每个i遍历所有j，时间复杂度较高。可以使用双指针技术优化：

    • 由于两个数组都是有序的，可以维护一个指针在b数组中移动
    • 对于当前的i，找到第一个满足j≥i-k的位置，然后检查是否存在j≤i+k

  3. 二分查找优化：另一种优化方法是对每个匹配a的索引i，在匹配b的索引数组中二分查找范围[i-k, i+k]内的元素。

推荐使用双指针方法，因为实现简单且效率高。时间复杂度为O(n + |indices_a| + |indices_b|)，其中n是字符串长度。

代码实现

class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        vector<int> indices_a, indices_b;
        
        // Find all indices where string a matches
        for (int i = 0; i <= (int)s.length() - (int)a.length(); i++) {
            if (s.substr(i, a.length()) == a) {
                indices_a.push_back(i);
            }
        }
        
        // Find all indices where string b matches
        for (int i = 0; i <= (int)s.length() - (int)b.length(); i++) {
            if (s.substr(i, b.length()) == b) {
                indices_b.push_back(i);
            }
        }
        
        vector<int> result;
        int j = 0;
        
        for (int i : indices_a) {
            // Move j to the first position where indices_b[j] >= i - k
            while (j < indices_b.size() && indices_b[j] < i - k) {
                j++;
            }
            
            // Check if there exists a j such that |i - indices_b[j]| <= k
            if (j < indices_b.size() && indices_b[j] <= i + k) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        indices_a = []
        indices_b = []
        
        # Find all indices where string a matches
        for i in range(len(s) - len(a) + 1):
            if s[i:i + len(a)] == a:
                indices_a.append(i)
        
        # Find all indices where string b matches
        for i in range(len(s) - len(b) + 1):
            if s[i:i + len(b)] == b:
                indices_b.append(i)
        
        result = []
        j = 0
        
        for i in indices_a:
            # Move j to the first position where indices_b[j] >= i - k
            while j < len(indices_b) and indices_b[j] < i - k:
                j += 1
            
            # Check if there exists a j such that |i - indices_b[j]| <= k
            if j < len(indices_b) and indices_b[j] <= i + k:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> BeautifulIndices(string s, string a, string b, int k) {
        List<int> indicesA = new List<int>();
        List<int> indicesB = new List<int>();
        
        // Find all indices where string a matches
        for (int i = 0; i <= s.Length - a.Length; i++) {
            if (s.Substring(i, a.Length) == a) {
                indicesA.Add(i);
            }
        }
        
        // Find all indices where string b matches
        for (int i = 0; i <= s.Length - b.Length; i++) {
            if (s.Substring(i, b.Length) == b) {
                indicesB.Add(i);
            }
        }
        
        List<int> result = new List<int>();
        int j = 0;
        
        foreach (int i in indicesA) {
            // Move j to the first position where indicesB[j] >= i - k
            while (j < indicesB.Count && indicesB[j] < i - k) {
                j++;
            }
            
            // Check if there exists a j such that |i - indicesB[j]| <= k
            if (j < indicesB.Count && indicesB[j] <= i + k) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var beautifulIndices = function(s, a, b, k) {
    const aIndices = [];
    const bIndices = [];
    
    // Find all indices where pattern 'a' occurs
    for (let i = 0; i <= s.length - a.length; i++) {
        if (s.substring(i, i + a.length) === a) {
            aIndices.push(i);
        }
    }
    
    // Find all indices where pattern 'b' occurs
    for (let i = 0; i <= s.length - b.length; i++) {
        if (s.substring(i, i + b.length) === b) {
            bIndices.push(i);
        }
    }
    
    const beautiful = [];
    
    // For each 'a' index, check if there's a 'b' index within distance k
    for (const i of aIndices) {
        for (const j of bIndices) {
            if (Math.abs(j - i) <= k) {
                beautiful.push(i);
                break;
            }
        }
    }
    
    return beautiful;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n × (
空间复杂度O(