Find All Anagrams in a String
程序员文章站
2022-03-21 21:21:55
...
1. 解析
题目大意,在字符串中查找给定的子序列,该子序列只要求出现的字符相同,而不要求顺序一样。
2. 分析
整体上,这道题还是比较容易想到的。每次在s串中切割长度和p相同的字符串,然后比较它们出现的字符是否相同,如果一样,记录起点的位置;如果不一样,说明两个子串不相等。将字符串往后移动,逐个切割判断即可。这里的关键是如果判断两个子串出现的字符是一样的,我刚开始想到的解法是,分别将这两个子串进行排序,这样就可以直接比较了,但这种方法是过不了OJ的,因为当子串p特别大的时候,调用系统的sort算法是特别耗时的。最好的做法无非就是利用数组进行存储,因为字符串都是由26个小写组成,所以我们只需建立一个26个长度的序列就可以表示它们出现的情况。用数组的下标表示出现的字符,即'a'就是0,'b'就是1,......,以此类推。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int p_len = p.length();
vector<int> res;
if (s.length() < p_len) return res; //如果查找的子串的长度大于母串
vector<int> s_count(26, 0);
vector<int> p_count(26, 0);
for (int i = 0; i < p_len; ++i){ //记录待查找字符串p的字符出现次数以及在字符串s中前p字符串长度的字符出现个数
++s_count[s[i]-'a'];
++p_count[p[i]-'a'];
}
if (s_count == p_count) res.push_back(0);
for (int i = p_len; i < s.length(); ++i){
--s_count[s[i-p_len]-'a'];
++s_count[s[i]-'a'];
if (s_count == p_count)
res.push_back(i-p_len+1);
}
return res;
}
};
滑动窗口解法:
left-----窗口的左边界,right-------窗口的右边界,cnt-----要匹配的字符总数,m------存储字符串p中字符出现的个数
当字符串s中的某段字串出现的字符和p中出现的一样时,cnt就会变成0,将左边界left记录下来;当窗口的大小大于设定的大小时,要将左边界右移,同时判断左边界出现的字符是否在p中,如果存在,去掉后,意味着要匹配的字符个数要增加1个(关键的地方)。
class Solution {
public:
vector<int> findAnagrams(string s, string p){
vector<int> res;
vector<int> m(26, 0);
for (char ch : p) ++m[ch-'a']; //记录p串中每个字符出现的次数
int left = 0, right = 0, len = s.length(), cnt = p.length();
while (right < len) { //维持的整个窗口大小为子串p的长度
if (m[s[right++]-'a']-- >= 1) cnt--;
if (cnt == 0) res.push_back(left); //若当前p出现的字符都被匹配,则意味着出现相同的子串
if (right - left == p.length() && m[s[left++]-'a']++ >= 0) cnt++; //若当前窗口的大小比设定窗口大1,则左边界往右移动
}
return res;
}
};
上一篇: 【C#WPF】style
下一篇: Uniapp项目—商城分类页
推荐阅读
-
训练YOLOV3报错TypeError: not all arguments converted during string formatting
-
深入C++ string.find()函数的用法总结
-
Google App Engine (Java + String + Velocity)数据访问调试,出现错误 Cannot find class [javax
-
Status bar could not find cached time string image. Rendering in-process?
-
LeetCode448 — Find All Numbers Disappeared in an Array
-
LeetCode442 — Find All Duplicates in an Array
-
leetcode 448. Find All Numbers Disappeared in an Array
-
LeetCode-448. Find All Numbers Disappeared in an Array
-
Leetcode 448. Find All Numbers Disappeared in an Array (python+cpp)
-
LeetCode之Find All Duplicates in an Array