HackMD
438.Find All Anagrams in a String
tags: Medium,String,Hash Table,Sliding Window
438. Find All Anagrams in a String
題目描述
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
範例
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".
Constraints:
- 1 <=
s.length,p.length<= 3 * 104 sandpconsist of lowercase English letters.
解答
C++
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> sc(26, 0), pc(26, 0), ans;
if (s.size() < p.size()) return ans;
for (int i = 0; i < p.size(); i++) {
pc[p[i] - 'a']++;
sc[s[i] - 'a']++;
}
if (pc == sc) ans.push_back(0);
for (int i = p.size(); i < s.size(); i++) {
sc[s[i] - 'a']++;
sc[s[i - p.size()] - 'a']--;
if (pc == sc) ans.push_back(i - p.size() + 1);
}
return ans;
}
};
Yen-Chi ChenSun, Feb 5, 2023
Python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
if len(s) < len(p): return ans
sc, pc = Counter(s[:len(p)]), Counter(p)
if sc == pc: ans.append(0)
for i in range(len(p), len(s)):
sc[s[i]] += 1
sc[s[i - len(p)]] -= 1
if sc == pc: ans.append(i - len(p) + 1)
return ans
Yen-Chi ChenSun, Feb 5, 2023
Javascript
function findAnagrams(s, p) {
let left = 0;
let right = 0;
let count = p.length;
const map = [];
const result = [];
for (const char of p) {
if (!map[char]) {
map[char] = 1;
} else {
map[char]++;
}
}
while (right < s.length) {
if (map[s[right]] > 0) {
count--;
}
map[s[right]]--;
right++;
if (count === 0) {
result.push(left);
}
if (right - left === p.length) {
if (map[s[left]] >= 0) {
count++;
}
map[s[left]]++;
left++;
}
}
return result;
}
MarsgoatSun, Feb 5, 2023
