题目描述
给你一个下标从 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
以数组形式按 从小到大排序 返回美丽下标。
样例
输入: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] 作为结果。
输入: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
只包含小写英文字母。
算法
(暴力枚举,双指针) $O(nm)$
- 分别暴力匹配出 $a$ 和 $b$ 的下标位置,记为 $ma$ 和 $mb$。
- 对于 $ma$ 中的每个位置 $i$,都对应 $mb$ 的一个区间 $[j_1, j_2)$,如果 $j_1 < j_2$,则 $ma(i)$ 是合法下标。
- 注意到 $j_1$ 和 $j_2$ 都是随着 $i$ 增大而单调不减的。
时间复杂度
- 假设 $n = s.length, m = \max(a.length, b.length)$,则暴力匹配的时间复杂度为 $O(nm)$,双指针的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(nm)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储匹配的下标位置。
C++ 代码
class Solution {
private:
vector<int> find(const string &s, const string &p) {
const int n = s.size(), m = p.size();
vector<int> res;
for (int i = 0; i < n; i++)
if (s.substr(i, m) == p)
res.push_back(i);
return res;
}
public:
vector<int> beautifulIndices(string s, string a, string b, int k) {
vector<int> ma = find(s, a);
vector<int> mb = find(s, b);
vector<int> ans;
for (int i = 0, j1 = 0, j2 = 0; i < ma.size(); i++) {
while (j1 < mb.size() && mb[j1] + k < ma[i]) ++j1;
while (j2 < mb.size() && mb[j2] <= ma[i] + k) ++j2;
if (j1 < j2)
ans.push_back(ma[i]);
}
return ans;
}
};