找出数组中的美丽下标 II
难度:
标签:
题目描述
You are given a 0-indexed string s, a string a, a string b, and an integer k.
An index i is beautiful if:
0 <= i <= s.length - a.lengths[i..(i + a.length - 1)] == a- There exists an index
jsuch that:0 <= j <= s.length - b.lengths[j..(j + b.length - 1)] == b|j - i| <= k
Return the array that contains beautiful indices in sorted order from smallest to largest.
Example 1:
Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 Output: [16,33] Explanation: There are 2 beautiful indices: [16,33]. - The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15. - The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15. Thus we return [16,33] as the result.
Example 2:
Input: s = "abcd", a = "a", b = "a", k = 4 Output: [0] Explanation: There is 1 beautiful index: [0]. - The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4. Thus we return [0] as the result.
Constraints:
1 <= k <= s.length <= 5 * 1051 <= a.length, b.length <= 5 * 105s,a, andbcontain only lowercase English letters.
代码结果
运行时间: 344 ms, 内存: 52.3 MB
/*
题目思路：
1. 使用 IntStream 生成所有可能的 i 和 j。
2. 过滤出符合 a 和 b 的子字符串。
3. 检查 |j - i| 是否小于等于 k。
4. 将结果收集并排序。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class BeautifulIndicesStream {
public List<Integer> findBeautifulIndices(String s, String a, String b, int k) {
int sLength = s.length();
int aLength = a.length();
int bLength = b.length();
return IntStream.range(0, sLength - aLength + 1)
.filter(i -> s.substring(i, i + aLength).equals(a))
.filter(i -> IntStream.range(0, sLength - bLength + 1)
.anyMatch(j -> s.substring(j, j + bLength).equals(b) && Math.abs(i - j) <= k))
.boxed()
.sorted()
.collect(Collectors.toList());
}
public static void main(String[] args) {
BeautifulIndicesStream bis = new BeautifulIndicesStream();
String s = "isawsquirrelnearmysquirrelhouseohmy";
String a = "my";
String b = "squirrel";
int k = 15;
System.out.println(bis.findBeautifulIndices(s, a, b, k)); // 输出: [16, 33]
}
}解释
方法:
本题解的主要思路是找出所有满足特定条件的下标对。首先，使用辅助函数g来找到字符串a或b中最小的重复模式长度，这有助于后续的优化。函数f0是用来找出字符串s中所有包含字符串a或b的起始下标。函数f用于优化搜索过程，如果字符串a或b有重复的模式，f会尽量减少搜索次数，从而只搜索可能的开始下标。最后，根据这些起始下标，检查它们之间的距离是否满足条件k。如果a和b是同一个字符串，可以进一步减少计算量。最终，将满足条件的下标存入结果数组并返回。
时间复杂度:
O(n * m)
空间复杂度:
O(n)
代码细节讲解
🦆
在实现函数`g`时，如何确保找到的是最小的重复模式长度，这里的递归逻辑是否可能导致重复检查某些长度？
▷🦆
函数`f0`中，当找到一个匹配的索引后，为什么要将索引`i`加1再继续搜索，这样会不会漏掉某些重叠的匹配情况？
▷🦆
对于函数`f`，如何决定使用优化搜索而不是简单的全搜索，特别是当字符串`a`和`b`很短时，这个优化是否仍然有效？
▷