438. Find All Anagrams in a String

题目描述和难度

  • 题目描述:

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

思路分析

求解关键:

参考解答

参考解答1:我用了比较长的时间才把这个解答写清楚,确实有点绕。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {


    // 使用滑动窗口的方式解决,标记为简单哦
    // s = "cbaebabacd",p = "abc"
    // 参考资料:https://blog.csdn.net/chenwuji91/article/details/52981530

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        // 先考虑特殊情况
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return res;
        }

        // 这个 hash 表记录了每个字母出现的频率,即计数值
        // ASCII 的长度是 256 位

        int[] hash = new int[256];

        // 滑动窗口的左边界
        int l = 0;
        // 滑动窗口的右边界
        int r = 0;
        // 滑动窗口的长度
        int distance = p.length();
        for (char c : p.toCharArray()) {
            hash[c]++;
        }

        int sLen = s.length();
        while (r < sLen) {
            if (hash[s.charAt(r)] > 0) {
                // 吸纳进来以后,说明差距减少 1
                distance--;
            }
            // 如果是等于 0 的就说明没有出现在 p 中,也 --,以后左边界扫到它的时候,就知道它不在 p 指定的范围中了
            // 不管当前字符在不在 hash 表中,都适用于这个逻辑(听下来想想为什么)
            hash[s.charAt(r)]--;
            r++;
            if (distance == 0) {
                // 差距为 0 了,就表示是一个结果,左端点加入结果集
                res.add(l);
            }
            if (r - l == p.length()) {
                // 大于等于 0 的,说明字符在 p 中,那些是负的字符说明不在 p 中
                if (hash[s.charAt(l)] >= 0) {
                    // 差距又拉大了 1
                    // 左端点离开滑动窗口,差距加大 1
                    distance++;
                }
                // 左端点离开滑动窗口
                // 不管 字符 在不在 p 中,都适用于这个逻辑
                hash[s.charAt(l)]++;
                l++;
            }
        }
        // System.out.println(Arrays.toString(hash));
        return res;
    }

    // c b a e b a b a c d
    // 0 1 2 3 4

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> anagrams = solution.findAnagrams(s, p);
        System.out.println(anagrams);
    }
}

参考解答2:和参考解答1 一样的写法,只不过使用了更少的空间。

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        // 因为题目中说,只有 26 个英文小写字母
        int[] chars = new int[26];
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return res;
        }
        for (char c : p.toCharArray()) {
            chars[c - 'a']++;
        }
        int left = 0;
        int right = 0;
        int distance = p.length();
        while (right < s.length()) {
            if (chars[s.charAt(right) - 'a'] > 0) {
                distance--;
            }
            chars[s.charAt(right) - 'a']--;
            right++;
            if (distance == 0) {
                res.add(left);
            }

            if (right - left == p.length()) {
                if (chars[s.charAt(left) - 'a'] >= 0) {
                    distance++;
                }
                chars[s.charAt(left) - 'a']++;
                left++;
            }
        }
        return res;
    }
}

参考解答3:

import java.util.ArrayList;
import java.util.List;

public class Solution3 {

    // 参考了小 Q 的思路,其实还是滑动窗口

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] cntp = new int[256];
        int[] cnts = new int[256];
        for (char c : p.toCharArray()) {
            cntp[c]++;
        }
        int same = 0;
        for (int i = 0; i < 256; i++) {
            if (cntp[i] == 0) {
                same++;
            }
        }
        int plen = p.length();
        int slen = s.length();
        for (int i = 0; i < slen; i++) {
            int curChar = s.charAt(i);
            cnts[curChar]++;
            if (cnts[curChar] == cntp[curChar]) {
                same++;
            } else if (cnts[curChar] == cntp[curChar] + 1) {
                // 超过了 same 就减 1,再超过反正已经减了 1 ,就不用再减了
                same--;
            }
            // 当 i>= p.lenght() 的时候,左边窗口要考虑左移了
            if (i >= plen) {
                int deleteChar = s.charAt(i - plen);
                cnts[deleteChar]--;
                if (cnts[deleteChar] == cntp[deleteChar]) {
                    same++;
                } else if (cnts[deleteChar] == cntp[deleteChar] - 1) {
                    // 超过了 same 就减 1,再超过反正已经减了 1 ,就不用再减了
                    same--;
                }
            }
            if (same == 256) {
                res.add(i - plen + 1);
            }
        }
        return res;
    }
}

参考解答4:和参考解答3 一样的写法,只不过使用了更少的空间。

import java.util.ArrayList;
import java.util.List;

public class Solution5 {

    // 这种解法从语义上更好理解一些

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        int[] cntp = new int[26];
        int[] cnts = new int[26];

        int plen = p.length();
        int slen = s.length();

        // 数组 cntp 在预处理以后是没有变化的
        for (int i = 0; i < plen; i++) {
            cntp[p.charAt(i) - 'a']++;
        }

        int same = 0;
        for (int i = 0; i < 26; i++) {
            if (cntp[i] == 0) {
                same++;
            }
        }

        for (int i = 0; i < slen; i++) {
            char curChar = s.charAt(i);
            cnts[curChar - 'a']++;
            if (cnts[curChar - 'a'] == cntp[curChar - 'a']) {
                same++;
            } else if (cnts[curChar - 'a'] == cntp[curChar - 'a'] + 1) {
                same--;
            }

            if (i >= plen) {
                int deleteIndex = i - plen;
                char deleteChar = s.charAt(deleteIndex);
                cnts[deleteChar - 'a']--;
                if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a']) {
                    same++;
                } else if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a'] - 1) {
                    same--;
                }
            }

            if (same == 26) {
                res.add(i - plen + 1);
            }
        }
        return res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0438-find-all-anagrams-in-a-string ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com