网站审批号dedeai网站最新

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