使用 oh-my-zsh

题目

给定两个字符串 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 * 10^4$
• s 和 p 仅包含小写字母

分析

通过滑动窗口，我们取找到匹配p字符的子串，然后找下一个子串的位置。

代码

滑动窗口

p串哈希化，然后滑动p.length的窗口。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // p 串预处理
        char[] chars = p.toCharArray();
        Arrays.sort(chars);

        int[] charInts = new int[26];
        for (char ch : chars) {
            charInts[ch - 'a']++;
        }

        // 滑动窗口识别目标子串
        int l = 0, r = 0;
        List<Integer> ans = new ArrayList<>();
        while (l < s.length() - p.length() + 1) {
            // 移除明显不符合异构的case
            if (charInts[s.charAt(l) - 'a'] > 0) {
                // copy p串的hash统计
                int[] temp = Arrays.copyOf(charInts, 26);
                int count = 0;
                // 获取子串
                char[] char1 = s.substring(l, l + chars.length).toCharArray();
                // 逐个匹配
                for (int i = 0; i < char1.length; i++) {
                    if (temp[char1[i] - 'a'] > 0) {
                        count++;
                        temp[char1[i] - 'a']--;
                    } else {
                        count = 0;

                        break;
                    }
                }
                // count = p.length() 说明是异构串，添加下标到结果
                if (count == p.length()) {
                    ans.add(l);
                }
            }
            l++;
        }

        return ans;
    }
}

窗口哈希化

对窗口构建hash存储。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 左右指针
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        // 数组哈希存储字符的计数
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        // 判断刚开始是否找到异构子串
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        // 逐个遍历，窗口大小是pLen
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            // 找到异构字符串
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

优化窗口对比的方法

窗口的异同，采用差分法判断异构字符串。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        // 查分法
        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];
            
            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com