题目描述
给你一个下标从 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 只包含小写英文字母。
思路 && 解题方法
使用kmp 定位字符串在s中出现的索引,然后比对两组索引的索引差是否在k之内,考虑到两组索引是有序的,可以使用二分查找加速。
描述你的解题方法
复杂度
时间复杂度:
示例: $O(n+m)$
空间复杂度:
示例: $O(n+m)$
Code
class Solution {
public:
int n, m;
vector<int> ne;
//kmp 模版 找出的索引放在vector 返回
vector<int> find(const string& s, const string& p) {
ne.resize(500010, 0);
vector<int> ret;
m = s.size() - 1; n = p.size() - 1;
for (int i = 2, j = 0; i <= n; i++)
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == n)
{
//printf("%d ", i - n);
ret.push_back(i - n);
j = ne[j];
}
}
return ret;
}
vector<int> beautifulIndices(string s, string a, string b, int k) {
//kmp模版使用的从1索引开始计数 所以前面插入一个符号
s.insert(s.begin(), '#'); a.insert(a.begin(), '@'); b.insert(b.begin(), '&');
vector<int> aret = find(s, a);
vector<int> bret = find(s, b);
if (aret.empty() || bret.empty()) return vector<int>();
vector<int> ans;
//遍历a的符合条件的索引 再二分查找b符合条件的索引 进行检测是否在k的范围以内
for (int i = 0; i < aret.size(); i++) {
int val = aret[i];
int find = upper_bound(bret.begin(), bret.end(), val) - bret.begin();
if (find >= bret.size()) {
find--;
}
if (abs(bret[find] - val) <= k ||
(find - 1 >= 0 && abs(bret[find - 1] - val) <= k )) {
ans.push_back(aret[i]);
}
}
return ans;
}
};
那个困难版本需要kmp,简单的暴力
嗯,收到。 不过一个题解写两个题 简单的爽快感. 哈哈