438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。说明：字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。示例 1:输入:s: "cbaebabacd" p: "abc"输出:[0, 6]解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。示例 2:输入:s: "abab" p: "ab"输出:[0, 1, 2]解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
滑动窗口
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 用于返回字母异位词的起始索引
List<Integer> res = new ArrayList<>();
// 用 map 存储目标值中各个单词出现的次数
HashMap<Character, Integer> map = new HashMap<>();
for (Character c : p.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
// 用另外一个 map 存储滑动窗口中有效字符出现的次数
HashMap<Character, Integer> window = new HashMap<>();
int left = 0;
int right = 0;
// 只有当 valid == p.length 时，才说明 window 中包含了目标子串
int valid = 0;
while (right < s.length()) {
// 如果目标子串中包含了该字符，才存入 window 中
if (map.containsKey(s.charAt(right))) {
window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
// 只有当 window 中该有效字符数量不大于map中该字符数量，才能算一次有效包含
if (window.get(s.charAt(right)) <= map.get(s.charAt(right))) {
valid++;
}
}
// 如果 window 符合要求，即两个 map 存储的有效字符相同，就可以移动左指针了
// 但是只有二个map存储的数据完全相同，才可以记录当前的起始索引，也就是left指针所在位置
while (valid == p.length()) {
if (right - left + 1 == p.length()) {
res.add(left);
}
// 如果左指针指的是有效字符,需要更改 window 中的 key 对应的 value
// 如果 有效字符对应的数量比目标子串少，说明无法匹配了
if (map.containsKey(s.charAt(left))) {
window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
if (window.get(s.charAt(left)) < map.get(s.charAt(left))) {
valid--;
}
}
left++;
}
right++;
}
return res;
}
}
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
示例 2：
输入：s = “a”, t = “a”
输出：”a”
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
滑动窗口
- 统计t中字符的次数
- 滑动窗口遍历s，right++，如果匹配到了一个t中的字符，match++;如果match =t.length()，尝试缩小左边界,left++
class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
// 定义一个数字，用来记录字符串 t 中出现字符的频率，也就是窗口内需要匹配的字符和相应的频率
int[] map = new int[128];
for (char c : t.toCharArray()) {
map[c]++;
}
int left = 0, right = 0;
int match = 0; // 匹配字符的个数
int minLen = s.length() + 1; // 最大的子串的长度
// 子串的起始位置 子串结束的位置(如果不存在这样的子串的话，start，end 都是 0，s.substring 截取就是 “”
int start = 0, end = 0;
int slength = s.length();
int tlength = t.length();
while (right < slength){
char charRight = s.charAt(right); // 右边界的那个字符
map[charRight]--; // 可以理解为需要匹配的字符 charRight 减少了一个
// 如果字符 charRight 在 t 中存在，那么经过这一次操作，只要个数大于等于 0，说明匹配了一个
// 若字符 charRight 不在 t 中，那么 map[charRight] < 0, 不进行任何操作
if (map[charRight] >= 0) match++;
right++; // 右边界右移，这样下面就变成了 [)，方便计算窗口大小
// 只要窗口内匹配的字符达到了要求，右边界固定，左边界收缩
while (match == tlength){
int size = right - left;
if (size < minLen){
minLen = size;
start = left;
end = right;
}
char charLeft = s.charAt(left); // 左边的那个字符
map[charLeft]++; // 左边的字符要移出窗口
// 不在 t 中出现的字符，移出窗口，最终能够达到的最大值 map[charLeft] = 0
// 如果恰好移出了需要匹配的一个字符，那么这里 map[charLeft] > 0, 也就是还要匹配字符 charLeft，此时 match--
if (map[charLeft] > 0) match--;
left++; // 左边界收缩
}
}
return s.substring(start, end);
}
}
若有收获，就点个赞吧
0 人点赞
