9.找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词

 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

 示例 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" 的异位词。

 提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

  思路1——定长滑动窗口

列表比较，实现可以计数也可以判断有哪些 cnS  cnP

使用定长滑动窗口，右端从0开始遍历s ，可以实现遍加入元素边比较。因此需要做到当左端 left<0 时，不处理比较和左端“出栈”。

        // 按照惯性思维应该是先左边出 再右边近。这样得保证right从p.length()处开始【p长度为三，right就从3开始，left从0开始】，需要多一步先赋值前p.length() 的s'【逻辑清晰 代码复杂一点，多一步赋值】

        // 按照下面代码可以实现，left<0时跳过比较和左端出，实现小于0时只进窗口。

 

注意：p.toCharArray() 字符串转数组；

s.charAt( i ) s 中下标为 i 的字符；

int[] index = new int[]; 为什么不能采用数组方式定义？？——> 这样定义会报错，因为是固定长度又没有传参数告知多长。明显题目中长度是不固定的

数组和 List 的核心区别：数组是固定长度、通过下标操作；List（ArrayList）是动态长度、通过 add()/get() 等方法操作

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnS = new int[26];
        int[] cnP = new int[26];
        // int[] index = new int[];  为什么不能采用这种方式定义？？
        List<Integer> ans = new ArrayList<>();
        int left = 0;
        // cnP 统计p中字母
        for(char ss : p.toCharArray()){
            cnP[ss-'a']++;
        }

        // cnS 统计s 的子串s'的字母
        // 按照惯性思维应该是先左边出 再右边近。这样得保证right从p.length()处开始【p长度为三，right就从3开始，left从0开始】，需要多一步先赋值前p.length() 的s'【逻辑清晰 代码复杂一点，多一步赋值】
        // 按照下面代码可以实现，left<0时跳过比较和左端出，实现小于0时只进窗口。
        //定长窗口可以考虑先进后出。【针对本题】
        for(int right = 0; right < s.length(); right++){
            cnS[s.charAt(right) - 'a']++;   // 右端进入窗口
            left = right - p.length() + 1;
            if(left<0) continue;

            if(Arrays.equals(cnS ,cnP)){
                ans.add(left);
            }
            cnS[s.charAt(left) - 'a']--;    // 左端出窗口
        }
        return ans;
    }
}

 

思路2——不定长滑动窗口【作者：灵茶山艾府 来源：力扣（LeetCode）】

枚举子串 s ′  的右端点，如果发现 s ′  其中一种字母的出现次数大于 p 的这种字母的出现次数，则右移 s ′  的左端点（缩小窗口）。如果发现 s ′  的长度等于 p 的长度，则说明 s ′  的每种字母的出现次数，等于 p 的每种字母的出现次数，即 s ′  是 p 的异位词。

只判断窗口右端字母：
cnt[ ] 用于记录字符元素出现哪些，出现几次。先遍历 p ,cnt[i]+1；再遍历s cnt[i] - 1。当cnt[i]<0时，说明p中没有这个字符，或者p中这个字符的数量没有s’ 多。

这时候就需要缩小窗口，直到cnt[i]>=0【cnt 回到加入字符 i 前的状态，同时left 窗口左端 移动到字符i 后一个位置 】

注意： while 部分有点绕，left  初始为0，当出现不匹配字符时候再回出来复原 cnt 调整窗口左端，将窗口左端移动到不匹配字符的下一个位置。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnt = new int[26];
        List<Integer> ans = new ArrayList<>();
        int left = 0;
        // cnt 统计p中字母。拿着cnt当模板比较s'
        for(char ss : p.toCharArray()){
            cnt[ss-'a']++;
        }

        for(int right = 0; right < s.length(); right++){
            int idx = s.charAt(right) - 'a';
            cnt[idx]--;   // 右端进入窗口

            while(cnt[idx] < 0){
                cnt[s.charAt(left)-'a']++; // 复原窗口，移动窗口左端
                left++;
            }

            if(right-left+1==p.length()) ans.add(left);

        }
        return ans;
    }
}