567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例 2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

注意：

  1. 输入的字符串只包含小写字母
  2. 两个字符串的长度都在 [1, 10,000] 之间

解题思路

滑动窗口
这种题目，是明显的滑动窗口算法，相当给你一个S和一个T，请问你S中是否存在一个子串，包含T中所有字符且不包含其他字符。

  1. class Solution {
  2. public:
  3.     bool checkInclusion(string s1, string s2) {//判断s2中是否存在s1的排列
  4.         unordered_map<char,int> window,need;
  5.         for (char c : s1) need[c]++;
  6.         int left = 0,right = 0;
  7.         int valid = 0;//窗口内符合要求的字符(字符对应的个数要符合)
  8.         while (right < s2.size()) {
  9.             char c = s2[right++];
  10.             //进行窗口内数据的一些列更新
  11.             if (need.count(c)) {
  12.                 window[c]++;
  13.                 if (window[c] == need[c]) valid++;
  14.             }
  15.             //判断左侧窗口是否要收缩
  16.             while (right - left >= s1.size()) {
  17.                 if (valid == need.size()) return true;//找到符合条件的子串，即可退出
  18.                 char d = s2[left++];
  19.                  //进行窗口内数据的一些列更新
  20.                  if (need.count(d)) {
  21.                     if(window[d] == need[d]) valid--;
  22.                     window[d]--;
  23.                  }
  24.             }
  25.         }
  26.         return false;//未找到符合条件的子串
  27.     }
  28. };