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

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

class Solution {

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> list = new ArrayList<>();

        if (s == null || p == null || s.length() < p.length())

            return list;

        int[] times = new int[26];

        char[] chs1 = s.toCharArray();

        char[] chs2 = p.toCharArray();

        for (char c : chs2)

            times[c - 'a']++;

        int[] temp = new int[26];

        for (int i = 0; i < p.length(); i++)

            temp[chs1[i] - 'a']++;

        if (compare(times, temp))

            list.add(0);

        for (int i = 0; i < s.length() - p.length(); i++) {

            char c = chs1[i + p.length()];

            char b = chs1[i];

            temp[c - 'a']++;

            temp[b - 'a']--;

            if (temp[c - 'a'] == times[c - 'a'] && temp[b - 'a'] == times[b - 'a']) {

                if (compare(times, temp))

                    list.add(i + 1);

            }

        }

        return list;

    }

    private boolean compare(int[] nums1, int[] nums2) {

        if (nums1.length != nums2.length)

            return false;

        for (int i = 0; i < nums1.length; i++) {

            if (nums1[i] != nums2[i])

                return false;

        }

        return true;

    }

}

Q438 找到字符串中所有字母异位词的相关教程结束。