力扣 438找到字符串中所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/

题目描述

题目分析

异位词所表示的空间 $\text{P}$ 即一字符串的所有排列,记${\mathbf{s}}_{\mathbf{i}}$为以$s[i]$开头的长度为$\text{plen}$的$s$子串
故本题可理解为求解$Ans$集合
A n s = {   i   ∣   s i ∈ P } Ans = \{\space i \space|\space\bold{s_i} \in{\text{P}}\} Ans={ i ∣ si​∈P}
难点：如何判断 ${\mathbf{s}}_{\mathbf{i}}$ 是否属于 $\text{P}$ 集合

题目解法

思路1：通过sort函数可唯一确定一异位词空间，如此可以判断 ${\mathbf{s}}_{\mathbf{i}}$ 是否属于题目要求的解空间 $\text{P}$

关键伪代码如下

sort(p);
for(...){
	temp <= s(i, plen);
	sort(temp);
	if(temp == p) ans.push(i);
}

思路2：通过count的方法唯一表示解空间

可以通过异位词的元素种类与对应个数唯一表示一异位词空间

代码如下

vector<int> findAnagrams(string s, string p) {
    int slen = s.length(), plen = p.length();
    vector<int> ans;
    if(s.length() < p.length()){
        return ans;
    }
    vector<int> hash_p(26);
    vector<int> hash_q(26);
    for(int i = 0; i < plen; ++i){
        ++hash_p[(p[i] - 'a')];
        ++hash_q[(s[i] - 'a')];
    }

    if(hash_p == hash_q) ans.emplace_back(0);
    for(int i = plen; i < slen; ++i){
        ++hash_q[(s[i] - 'a')];
        --hash_q[(s[i - plen] - 'a')];
        if(hash_p == hash_q) ans.emplace_back(i - plen + 1);
    }
    
    return ans;
}

总结

通过滑动窗口进行遍历，通过"hash"将字符串子串映射到异位词表示空间

每一个表示代表了一个异位词空间(一个字符串的所有元素的全排列)
广义上讲，以上方法都属于一种hash