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

前言

本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

题目链接

给定两个字符串 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 仅包含小写字母

思路

暴力解法： 判断一个字符串是否为异位词，最简单可以暴力排序，如果两个字符串排序后是一样的，则两个字符串为异位词。然后通过截取子字符串即可，最终提交超时，C++代码如下：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int size_s = s.size();
        int size_p = p.size();
        vector<int> ans;
        
        // 如果s的长度小于p的长度，直接返回空
        if (size_s < size_p) return ans;
        
        // 对p进行排序
        string sorted_p = p;
        sort(sorted_p.begin(), sorted_p.end());
        
        // 遍历s，检查每个长度为p.size()的子串
        for (int i = 0; i <= size_s - size_p; i++) {
            string substr = s.substr(i, size_p);  // 获取子串
            string sorted_substr = substr;  // 将子串复制一份进行排序
            sort(sorted_substr.begin(), sorted_substr.end());
            
            // 如果排序后的子串与p排序后的子串相同，则为异位词
            if (sorted_substr == sorted_p) {
                ans.push_back(i);  // 记录起始索引
            }
        }
        
        return ans;
    }
};

正规解法： 很经典的滑动窗口题目。控制跟字符串p一样的一个窗口在字符串s中滑动。然后判断是否存在异位词。判断的方法不能去用排序了，时间复杂度太高。可以去记录每个字符出现的次数（本题适用是因为字符串保证全为小写字母），然后调用字符串重写的equals方法去判断两个数组是否内容是相同的即可。写了一个Java版本，代码如下：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //滑动窗口
        int p_len = p.length();
        int s_len = s.length();
        if (s_len < p_len) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<Integer>();
        int[] s_count = new int[26];
        int[] p_count = new int[26];
        for (int i=0; i<p_len; i++){
            p_count[p.charAt(i) - 'a']++;
            s_count[s.charAt(i) - 'a']++;
        }
        for (int i=0; i<=s_len - p_len;i++){
            System.out.println(i);
            if (Arrays.equals(s_count, p_count)){//用重写的equals方法直接判断
                ans.add(i);
            }
            --s_count[s.charAt(i) - 'a'];
            //这个地方做一下特判，防止最后一个字符还去算下一次的状况
            if (i + p_len < s_len){
                ++s_count[s.charAt(i + p_len) - 'a'];
            }
        }
        return ans;
    }
}