Leetcode刷题java之438. 找到字符串中所有字母异位词-蒲公英云

Leetcode刷题java之438. 找到字符串中所有字母异位词

执行结果：

通过

显示详情

执行用时 :12 ms, 在所有 Java 提交中击败了68.92% 的用户

内存消耗 :38.3 MB, 在所有 Java 提交中击败了61.83%的用户

题目：

给定一个字符串 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” 的字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

参考https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<=0||s==null)
        {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> result=new ArrayList<>();
        int[] needs=new int[26];
        int[] windows=new int[26];
        int left=0;
        int right=0;
        int count=p.length();
        for(char c:p.toCharArray())
        {
            needs[c-'a']++;
        }
        while(right<s.length())
        {
            //右边界的处理
            char R=s.charAt(right);
            if(needs[R-'a']>0)
            {
                windows[R-'a']++;
                if(windows[R-'a']<=needs[R-'a'])
                {
                    count--;
                }
            }
            //左边界的处理
            while(count==0)
            {
                if(right-left+1==p.length())
                {
                    result.add(left);
                }
                char L=s.charAt(left);
                if(needs[L-'a']>0)
                {
                    windows[L-'a']--;
                    if(windows[L-'a']<needs[L-'a'])
                    {
                        count++;
                    }
                }
                left++;
            }
            right++;
        }
        return result;
    }
}