LeetCode 438. 找到字符串中所有字母异位词
原题链接
中等
作者:
JustDoIt11
,
2023-12-13 12:32:40
,
所有人可见
,
阅读 63
写的很好的一篇题解 :
https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/9749/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/?envType=study-plan-v2&envId=top-100-liked
package leetcode;
import java.util.*;
public class lec438 {
public static void main(String[] args) {
System.out.println(findAnagrams("cbaebabacd", "abc"));
}
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> lis = new ArrayList<>();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char x : p.toCharArray()) need.put(x, need.getOrDefault(x, 0) + 1);
// System.out.println(need);
int valid = 0, l = 0, r = 0;
while (r < s.length()) {
char x = s.charAt(r);
r ++ ; // 窗口移动
// date update 数据的更新
if (need.containsKey(x)) {
window.put(x, window.getOrDefault(x, 0) + 1);
if (need.get(x).equals(window.get(x))) valid ++ ;
}
// end
// debug 窗口为位置调试 窗口是左闭右开
System.out.println("window : " + "[" + l + ", " + r + ")" );
// end
// window shrink 窗口收缩
while (r - l >= p.length()) {
if (valid == need.size())
lis.add(l);
char d = s.charAt(l);
l ++ ;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid -- ;
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
// end
}
return lis;
}
}