华为 OD 训练营 · 题解精讲
LC438. 找到字符串中所有字母异位词
LC438. 找到字符串中所有字母异位词
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 示例 1: 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2: 输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。 提示: 1 <= s.length, p.length <= 3 * 10^4 s 和 p 仅包含小写字母
题目解析
参考代码（吴师兄）
1、Java 代码 // 登录 AlgoMooc 官网获取更多算法图解 // https://www.algomooc.com // 作者：程序员吴师兄 // 微信：wzb_3377 // 代码有看不懂的地方一定要私聊咨询吴师兄呀 // 找到字符串中所有字母异位词（LeetCode 438）:https://leetcode.cn/problems/find-all-anagrams-in-a-string/ class Solution { public List<Integer> findAnagrams(String s, String p) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型 List<Integer> res = new ArrayList<>();
// 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀 // needs 代表 p 中每个字符出现的频次 int[] needs = new int[26];
for(char ch : p.toCharArray()){ // 对于数组类型，其下标为 int 类型 // 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码 // 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次 needs[ch - 'a']++; }
// window 代表在滑动窗口中每个字符出现的频次 int[] window = new int[26];
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始 int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部 for(int end = 0; end < s.length(); end++){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 获取此时将要加入到滑动窗口的元素 char cur = s.charAt(end);
// 这个字符的频次需要发生变化 window[cur - 'a'] ++;
// 加入之后，去对比一下 window 中 cur 这个字符是否满足要求 if(isSame(window,needs)){
// 相同情况下，找到一个符合条件的索引 res.add(start); }
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, if( end >= p.length() - 1 ){
// 4.2、更新 (部分或所有) 维护变量 char chr = s.charAt(start);
// 最左端那个元素的频次发生变化 window[chr - 'a']--;
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变 start++;
}
}
// 【5、返回所需要的答案】 return res; }
boolean isSame (int[] a, int [] b){
for(int i = 0; i < a.length; i++){
if(a[i] != b[i])return false;
} return true; } }
2、C++ 代码 class Solution { public: vector<int> findAnagrams(string s, string p) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型 vector<int> res;
// 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀 // needs 代表 p 中每个字符出现的频次 vector<int> needs(26, 0);
for(auto& ch : p){ // 对于数组类型，其下标为 int 类型 // 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码 // 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次 needs[ch - 'a']++; }
// window 代表在滑动窗口中每个字符出现的频次 vector<int> window(26, 0);
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始 int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部 for(int end = 0; end < s.size(); end++){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 获取此时将要加入到滑动窗口的元素 auto cur = s[end];
// 这个字符的频次需要发生变化 window[cur - 'a']++;
// 加入之后，去对比一下 window 中 cur 这个字符是否满足要求 if(window == needs){
// 相同情况下，找到一个符合条件的索引 res.push_back(start); }
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, if( end >= p.size() - 1 ){
// 4.2、更新 (部分或所有) 维护变量 auto chr = s[start];
// 最左端那个元素的频次发生变化 window[chr - 'a']--;
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变 start++;
}
}
// 【5、返回所需要的答案】 return res; } };
3、Python 代码 class Solution: def findAnagrams(self, s: str, p: str) -> List[int]:
滑动窗口模板化解题，五步走策略
【1、定义需要维护的变量】
题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型
res = []
由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
needs 代表 p 中每个字符出现的频次
needs = [0] * 26
开始统计 t 中每个字符出现的频次
for ch in p:
对于数组类型，其下标为 int 类型
可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
idx = ord(ch) - ord('a') needs[idx] += 1
window 代表在滑动窗口中每个字符出现的频次
window = [0] * 26
【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
窗口的左端位置从 0 开始
start = 0
窗口的右端位置从 0 开始，可以一直移动到尾部
for end in range(len(s)):
【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
获取此时将要加入到滑动窗口的元素
cur = s[end]
这个字符的频次需要发生变化
window[ord(cur) - ord('a')] += 1
加入之后，去对比一下 window 中 cur 这个字符是否满足要求
if window == needs:
相同情况下，找到一个符合条件的索引
res.append(start)
【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if end >= len(p) - 1 :
4.2、更新 (部分或所有) 维护变量
chr = s[start]
最左端那个元素的频次发生变化
window[ord(chr) - ord('a')] -= 1
4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start += 1
【5、返回所需要的答案】
return res
参考代码（许老师滑动窗口三问三答模板）
1、Java 代码 class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>(); int np = p.length(), ns = s.length();
// 边界检查，如果 s 的长度小于 p，直接返回空结果 if (ns < np) return ans;
// 初始化第一个窗口的字符计数情况 int[] winCnt = new int[26]; // 窗口字符频率计数 int[] ansCnt = new int[26]; // p 的字符频率计数
// 填充初始窗口和 p 的字符频率 for (int i = 0; i < np; i++) { winCnt[s.charAt(i) - 'a']++; ansCnt[p.charAt(i) - 'a']++; }
// 检查初始窗口是否与 p 的频率匹配 if (Arrays.equals(winCnt, ansCnt)) { ans.add(0); }
// 滑动窗口，遍历 s 中剩余的字符 for (int right = np; right < ns; right++) { // A1: 将当前字符添加到窗口中 winCnt[s.charAt(right) - 'a']++;
// A2: 移除窗口左侧字符的影响 winCnt[s.charAt(right - np) - 'a']--;
// A3: 如果当前窗口的字符频率匹配 p，则记录起始索引 if (Arrays.equals(winCnt, ansCnt)) { ans.add(right - np + 1); } }
return ans; } }
2、C++ 代码 class Solution { public: std::vector<int> findAnagrams(std::string s, std::string p) { std::vector<int> ans; std::vector<int> cnt_p(26,0);
if (s.length() < p.length()) return ans;
for(char ch : p) { cnt_p[ch - 'a']++; }
int size_p = p.length(); std::vector<int> cntWindow(26,0); for(int i = 0; i < size_p; i++) { char ch = s[i]; cntWindow[ch-'a']++; } if(cntWindow == cnt_p) { ans.push_back(0); }
for(int right = size_p; right < s.length(); right++) { char rightCh = s[right]; cntWindow[rightCh - 'a']++;
int left = right - size_p; char leftCh = s[left]; cntWindow[leftCh - 'a']--;
if(cntWindow == cnt_p) { ans.push_back(left+1); }
} return ans; } };
3、Python 代码 class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: ans = list() np, ns = len(p), len(s)
初始化第一个窗口的情况
win_cnt = Counter(s[:np])
初始化p的情况
ans_cnt = Counter(p) if win_cnt == ans_cnt: ans.append(0) for right, ch in enumerate(s[np:], np):
A1
win_cnt[ch] += 1
A2
win_cnt[s[right-np]] -= 1
A3
if win_cnt == ans_cnt: ans.append(right-np+1) return ans