438. 找到字符串中所有字母异位词
一句话套路定长窗口 + 计数比较,进出各 O(1)
题目描述
给定两个字符串 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 * 104s和p仅包含小写字母
思路
时间
O(26·n)空间
O(1)思路
定长窗口(长度 = p.size())。每步右进一个、左出一个,维护 26 计数数组,和 need 比较即可。
窗口长度固定,所以用「进一个出一个」而不是 while 收缩。
优化
用 diff 计数「还有几个字母数量不对」可做 O(n),思路同 Q76。
图解
字符串
cbaebabacd(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0438 {
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
const int n = (int)s.size(), m = (int)p.size();
if (n < m) return ans;
vector<int> need(26, 0), win(26, 0);
for (char c : p) ++need[c - 'a'];
for (int i = 0; i < n; ++i) {
++win[s[i] - 'a']; // 右边进
if (i >= m) --win[s[i - m] - 'a']; // 左边出,维持定长
if (i >= m - 1 && win == need) ans.push_back(i - m + 1);
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0438::Solution s;
CHECK_EQ(s.findAnagrams("cbaebabacd", "abc"), vector<int>{0, 6});
CHECK_EQ(s.findAnagrams("abab", "ab"), vector<int>{0, 1, 2});
CHECK_EQ(s.findAnagrams("a", "aa"), vector<int>{}); // s 比 p 短
CHECK_EQ(s.findAnagrams("abcdef", "xyz"), vector<int>{});