HHot 100C++ 图解

438. 找到字符串中所有字母异位词

中等 滑动窗口 4 帧动画 在力扣上做

一句话套路定长窗口 + 计数比较,进出各 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 * 104
  • s 和 p 仅包含小写字母

思路

时间O(26·n)
空间O(1)

思路

定长窗口(长度 = p.size())。每步右进一个、左出一个,维护 26 计数数组,和 need 比较即可。

窗口长度固定,所以用「进一个出一个」而不是 while 收缩。

优化

用 diff 计数「还有几个字母数量不对」可做 O(n),思路同 Q76。

图解

c 0 b 1 a 2 e 3 b 4 a 5 b 6 a 7 c 8 d 9
字符串 cbaebabacd(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/03_sliding_window.cpp18 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q438_find_all_anagrams5 行
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>{});

↑↓ 选择↵ 打开/ 随时唤起