leetcode：567. 字符串的排列

题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例：

  1. 输入：s1 = "ab" s2 = "eidbaooo"
  2. 输出：true
  3. 解释：s2 包含 s1 的排列之一 ("ba").
  1. 输入：s1= "ab" s2 = "eidboaoo"
  2. 输出：false

解答 & 代码

滑动窗口写法一

滑动窗口，思路同：
[困难] 76. 最小覆盖子串
只有两点区别：

  1. 窗口左侧收缩的时机，变为窗口大小 >= s1 长度时。因为窗口要满足条件，就得是 s1 的一个排列，长度就应该等于 s1。右边界扩张到窗口大小 >= s1 长度时，如果不收缩下左边界，右边界继续扩张，窗口继续变大，不可能满足条件

  2. 在收缩窗口时判定是否找到了合法的窗口，即 validChCnt == needs.size()（此时等长，且包含字符相同，所以窗口是 s1 的一个排列）

    1. class Solution {
    2. public:
    3.  bool checkInclusion(string s1, string s2) {
    4.      unordered_map<char, int> needs;
    5.      unordered_map<char, int> window;
    6.      for(int i = 0; i < s1.size(); ++i)
    7.          ++needs[s1[i]];
    9.      int left = 0;
    10.      int right = 0;
    11.      int validChCnt = 0;
    12.      while(right < s2.size())
    13.      {
    14.          char c = s2[right];
    15.          ++right;
    16.          if(needs.find(c) != needs.end())
    17.          {
    18.              ++window[c];
    19.              if(window[c] == needs[c])
    20.                  ++validChCnt;
    21.          }
    23.          // 变化 1：窗口左侧收缩的时机，变为窗口大小 >= s1 长度时
    24.          // 因为窗口要满足条件，就得是 s1 的一个排列，长度就应该等于 s1
    25.          while(right - left >= s1.size())
    26.          {
    27.              // 变化 2：判断是否找到了合法的窗口
    28.              if(validChCnt == needs.size())
    29.                  return true;
    31.              char deleteC = s2[left];
    32.              ++left;
    33.              if(needs.find(deleteC) != needs.end())
    34.              {
    35.                  if(window[deleteC] == needs[deleteC])
    36.                      --validChCnt;
    37.                  --window[deleteC];
    38.              }
    39.          }
    40.      }
    41.      return false;
    42.  }
    43. };

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

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

执行结果：

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

滑动窗口写法二 [推荐]

上面的写法改变了窗口收缩时机。

下面的写法更加模板化，窗口收缩时机不变，唯一的改变就是判定窗口是否合法

  1. class Solution {
  2. public:
  3.     bool checkInclusion(string s1, string s2) {
  4.         unordered_map<char, int> need;
  5.         unordered_map<char, int> window;
  6.         for(int i = 0; i < s1.size(); ++i)
  7.             ++need[s1[i]];
  9.         int left = 0;
  10.         int right = 0;
  11.         int validCnt = 0;
  12.         while(right < s2.size())
  13.         {
  14.             char ch = s2[right];
  15.             ++right;
  17.             if(need.find(ch) != need.end())
  18.             {
  19.                 ++window[ch];
  20.                 if(window[ch] == need[ch])
  21.                     ++validCnt;
  22.             }
  24.             // 窗口收缩（左边界右移）
  25.             while(validCnt == need.size())
  26.             {
  27.                 // 唯一的变化：在这里判断是否找到了合法的窗口，即窗口长度 == s1 的长度
  28.                 if(right - left == s1.size())
  29.                     return true;
  31.                 char deleteCh = s2[left];
  32.                 ++left;
  34.                 if(need.find(deleteCh) != need.end())
  35.                 {
  36.                     --window[deleteCh];
  37.                     if(window[deleteCh] == need[deleteCh] - 1)
  38.                         --validCnt;
  39.                 }
  40.             }
  41.         }
  42.         return false;
  43.     }
  44. };

执行结果：

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