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

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例：

  1. 输入: s = "cbaebabacd", p = "abc"
  2. 输出: [0,6]
  3. 解释:
  4. 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
  5. 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
  1. 输入: s = "abab", p = "ab"
  2. 输出: [0,1,2]
  3. 解释:
  4. 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
  5. 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
  6. 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解答 & 代码

滑动窗口，思路同：
[中等] 567. 字符串的排列
p 的字母异位词就是 p 的字母排列，一个意思。和上题唯一的区别是，在找到符合条件的窗口时，上题是直接返回 true，这里则是将左指针存入结果数组。

  1. class Solution {
  2. public:
  3.     vector<int> findAnagrams(string s, string p) {
  4.         unordered_map<char, int> needs;
  5.         unordered_map<char, int> window;
  6.         for(int i = 0; i < p.size(); ++i)
  7.             ++needs[p[i]];
  9.         int left = 0;        // 左指针
  10.         int right = 0;        // 右指针
  11.         int validChCnt = 0;
  12.         vector<int> result;
  13.         while(right < s.size())
  14.         {
  15.             char ch = s[right];
  16.             ++right;
  17.             // 进行窗口内数据的更新
  18.             if(needs.find(ch) != needs.end())
  19.             {
  20.                 ++window[ch];
  21.                 if(window[ch] == needs[ch])
  22.                     ++validChCnt;
  23.             }
  24.             // cout << "window: [" << left << ", " << right << "]" << endl;
  26.             // 判断左侧窗口是否要收缩
  27.             while(right - left >= p.size())
  28.             {
  29.                 // 当窗口符合条件时，将窗口起始下标加入结果数组
  30.                 if(validChCnt == needs.size())
  31.                     result.push_back(left);
  33.                 char deleteC = s[left];
  34.                 ++left;
  35.                 // 进行窗口内数据的更新
  36.                 if(needs.find(deleteC) != needs.end())
  37.                 {
  38.                     if(window[deleteC] == needs[deleteC])
  39.                         --validChCnt;
  40.                     --window[deleteC];
  41.                 }
  42.                 // cout << "window: [" << left << ", " << right << "]" << endl;
  43.             }
  44.         }
  45.         return result;
  46.     }
  47. };

复杂度分析：设字符串 s 长为 N，字符串p 包含 C 个不同的字符

  • 时间复杂度 O(N)：最坏情况下，字符串 s 的每个字符分别被左、右指针遍历一次
  • 空间复杂度 O(C)：两个哈希表的空间复杂度都取决于字符串p 中不同字符的种数 C

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 28.20% 的用户
  4. 内存消耗：8.3 MB, 在所有 C++ 提交中击败了 92.82% 的用户