https://leetcode.cn/problems/find-all-anagrams-in-a-string/
题目描述
题目分析
异位词所表示的空间 P \text{P} P 即一字符串的所有排列,记 s i \bold{s_i} si为以 s [ i ] s[i] s[i]开头的长度为 plen \text{plen} plen的 s s s子串
故本题可理解为求解 A n s Ans Ans集合
A n s = { i ∣ s i ∈ P } Ans = \{\space i \space|\space\bold{s_i} \in{\text{P}}\} Ans={ i ∣ si∈P}
难点:如何判断 s i \bold{s_i} si 是否属于 P {\text{P}} P 集合
题目解法
思路1:通过sort
函数可唯一确定一异位词空间,如此可以判断 s i \bold{s_i} si 是否属于题目要求的解空间 P {\text{P}} 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