给定两个字符串s1,s2和正整数K,其中s1长度为n1,s2长度为n2,在s2中选一个子串,子串长度为n1+k,子串包含s1中全部字母,子串中每个字母出现的次数不小于s1中对应的字幕,我们称s2以长度k冗余覆盖s1,给定s1,s2,k,求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标,如果没有返回-1。java输出
时间: 2023-12-14 12:05:59 浏览: 44
以下是 Java 的代码实现:
```java
public static int findSubstring(String s1, String s2, int k) {
int n1 = s1.length(), n2 = s2.length();
int[] count1 = new int[26], count2 = new int[26];
for (int i = 0; i < n1; i++) {
count1[s1.charAt(i) - 'a']++;
}
for (int i = 0; i < n2; i++) {
if (i >= n1) {
count2[s2.charAt(i - n1) - 'a']--;
}
count2[s2.charAt(i) - 'a']++;
if (i >= n1 - 1) {
boolean flag = true;
for (int j = 0; j < 26; j++) {
if (count2[j] < count1[j]) {
flag = false;
break;
}
}
if (flag) {
return i - n1 + 1;
}
}
}
return -1;
}
```
其中,`count1` 和 `count2` 分别记录字符串 `s1` 和 `s2` 中每个字母出现的次数。我们使用滑动窗口的思想,依次枚举 `s2` 中长度为 `n1+k` 的子串,判断其中是否包含 `s1` 中全部字母,并且每个字母出现的次数不小于 `s1` 中对应的字母。如果找到了符合条件的子串,则返回它的首个元素的下标。如果遍历完整个 `s2`,仍然没有找到符合条件的子串,则返回 `-1`。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)