题目描述:给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指字母相同,但排列不同的字符串。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public List<Integer> findAnagrams(String s, String p) { Map<Character, Integer> need = new HashMap<>(); Map<Character, Integer> window = new HashMap<>(); for (int i = 0; i < p.length(); i++) { need.merge(p.charAt(i), 1, (oldVal, newVal) -> ++oldVal); }
int left = 0, right = 0, valid = 0; List<Integer> res = new ArrayList<>();
while (right < s.length()) { char r = s.charAt(right); right++; if (need.containsKey(r)) { window.merge(r, 1, (oldVal, newVal) -> ++oldVal); if (window.get(r).equals(need.get(r))) { valid++; } }
while (right - left == p.length()) { if (valid == need.size()) { res.add(left); } char l = s.charAt(left); left++; if (need.containsKey(l)) { if (window.get(l).equals(need.get(l))) { valid--; } window.compute(l, (k, v) -> --v); } } } return res; } }
|