【leetcode系列】567.字符串的排列（滑动窗口）

题目

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

换句话说，s1 的排列之一是 s2 的 子串 。

---

示例

示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false

---

思路1：dfs

使用集合统计s1的所有可能排列结果，然后挨个遍历，看是否在s2中

• 简单粗暴
• 容易超时

---

思路2：滑动窗口

前提：abc排列结果集6种：[abc，acb，bca，bac，cab，cba]。但是无论怎么排列，6种结果集中，一定是根据元素abc三个字符排列的。
所以，如果s1 = “abc”，我们只要判断s2中长度 = 3（abc的长度）的subStr子串，是否有包含abc三个字符的。有则说明包括。
比如s2 = “bbbca”，其中长度为3的子串bca，就由abc三个字符组成。所以就包含

步骤：

1、确定s1的长度len
2、使用滑动窗口，在s2中，扩张到len

• 此时，s1
• s2的子串sub2

3、判断：s2的subStr子串，是否由s1中字符组成 ：使用map判断
mapS1

• key：字符
• val：每个字符出现的次数
• abc：（a-1，b-1，c-1）

mapSub2

• key：字符
• val：每个字符出现的次数
• bbb（b-3）

如果mapS1中的所有key集合
key - v1
key - v2
都满足 v1 == v2，也就是说s1中的每个字符，都在sub2中，而且每个字符出现的频率和sub2一样，则说明s2的subStr子串，是由s1中字符组成的

4、举例：
s1：abc
s2：bbbca

• 第一个sub2：bbb，显然mapS1中（a-1，b-1，c-1），而mapS2中（b-3），不满足
• 窗口滑动得到第二个sub2：bbc，显然mapS2中（b-2，c-1），不满足
• 窗口滑动得到第三个sub2：bca，显然mapS2中（b-1，c-1，a-1），满足。
  和mapS1中每个元素，对应的val值（出现频率）都一样。说明找到了！

public class CheckS1DfsInS2 {public static void main(String[] args) {boolean b = checkInclusion("abc", "bbbca");System.out.println(b);}private static boolean checkInclusion(String s1, String s2) {if (s1 == null || s1.length() == 0) {return true;}if (s2 == null || s2.length() == 0 || s2.length() < s1.length()) {return false;}if (s1.length() == 1) {return s2.contains(s1);}Map<Character, Integer> mapS1 = new HashMap<>();int len1 = s1.length();for (int i = 0; i < len1; i++) {mapS1.merge(s1.charAt(i), 1, Integer::sum);}// 扩张到len1 - 1int i = 0;Map<Character, Integer> mapS2 = new HashMap<>();while (i < s1.length() - 1) {mapS2.merge(s2.charAt(i), 1, Integer::sum);i ++;}i = 0;for (int j = len1 - 1; j < s2.length(); j++) {mapS2.merge(s2.charAt(j), 1, Integer::sum);if (contain(mapS1, mapS2, s1)) {return true;} else {// 滑动char start = s2.charAt(i);Integer v2 = mapS2.get(start);mapS2.put(start, v2 - 1);i ++;}}return false;}private static boolean contain(Map<Character, Integer> mapS1, Map<Character, Integer> mapS2, String s1) {for (int k = 0; k < s1.length(); k++) {char s1Key = s1.charAt(k);Integer v1 = mapS1.get(s1Key);Integer v2 = mapS2.get(s1Key);if (v2 == null || ! v2.equals(v1)) {return false;}}return true;}
}