0438.找到字符串中所有字母异位词
方法一:滑动窗口
时间复杂度 $O(n)$,空间复杂度 $O(1)$。
impl Solution {
pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
let mut ans = Vec::new();
if p.len() > s.len() {
return ans;
}
let (s, p) = (s.as_bytes(), p.as_bytes());
let (mut s_cnt, mut p_cnt) = ([0; 26], [0; 26]);
for (i, &c) in p.iter().enumerate() {
s_cnt[(s[i] - b'a') as usize] += 1;
p_cnt[(c - b'a') as usize] += 1;
}
if s_cnt == p_cnt {
ans.push(0);
}
for i in p.len()..s.len() {
let (pre_idx, idx) = ((s[i - p.len()] - b'a') as usize, (s[i] - b'a') as usize);
s_cnt[idx] += 1;
s_cnt[pre_idx] -= 1;
if s_cnt == p_cnt {
ans.push((i - p.len() + 1) as i32);
}
}
ans
}
}