leetcode hot 100-438. 找到字符串中所有字母异位词

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

 1 class Solution {
 2     public List<Integer> findAnagrams(String s, String p) {
 3 
 4         // 对p串的每个字符进行hash计数
 5         int pLength = p.length();
 6         int sLength = s.length();
 7         int[] counts = new int[26];
 8         for(int i = 0; i < pLength; i++){
 9             counts[p.charAt(i) - ‘a‘]++;
10         }
11 
12         ArrayList<Integer> res = new ArrayList<>();
13         
14         // 从下标0开始遍历字符串s,对于每个下标，判断接下来长度为pLength的子串是否为目标串的字母异位词
15         for(int i = 0; i <= sLength - pLength; i++){
16             int[] tempCounts = Arrays.copyOf(counts, 26);
17             int j = i;
18             // 内部每次遍历p的长度个数的子串，把子串中每个字符的计数器减一，出现负数则进入下个子串的统计
19             for(; j < sLength && j < pLength + i; j++){
20                 if(--tempCounts[s.charAt(j) - ‘a‘] < 0){
21                     break;
22                 }
23             }
24             if(j >= pLength + i){  // 说明找到了一个符合条件的字母异位词
25                 res.add(i);
26             }
27         }
28         return res;
29     }
30 }