首页 > 代码库 > 438. Find All Anagrams in a String
438. Find All Anagrams in a String
438. Find All Anagrams in a String
- Total Accepted: 16658
- Total Submissions: 50116
- Difficulty: Easy
- Contributors: Stomach_ache
Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
先统计p中字符的个数,vector<int>(128,0).再从s的开头开始每次找p字符串长度个字符,来验证是否相同。如果不相同出现了直接break,如果一直都相同了,则将起始位置加入结果res中。
1 class Solution { 2 public: 3 vector<int> findAnagrams(string s, string p) { 4 vector<int> res; 5 if(s.empty()) return res; 6 vector<int> cnt(128, 0); 7 int ns = s.size(); 8 int np = p.size(); 9 for(int i = 0; i < np; i++){ 10 cnt[p[i] - ‘a‘]++; 11 //cnt[p[i]]++; 12 } 13 int i = 0; 14 while(i <= ns - np){ 15 vector<int> tmp = cnt; 16 bool success = true; 17 for(int j = i; j < i + np; j++){ 18 tmp[s[j] - ‘a‘]--; 19 //tmp[s[j]]--; 20 if(tmp[s[j] - ‘a‘] < 0){ 21 success = false; 22 break; 23 } 24 } 25 26 if(success) res.push_back(i); 27 i++; 28 } 29 return res; 30 } 31 };
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
438. Find All Anagrams in a String
My Submissions
- Total Accepted: 16658
- Total Submissions: 50116
- Difficulty: Easy
- Contributors: Stomach_ache
Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
438. Find All Anagrams in a String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。