題目

給你兩個字符串 s1 和 s2 ，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。

換句話說，s1 的排列之一是 s2 的 子串 。

---

示例

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

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

---

思路1：dfs

使用集合統(tǒng)計s1的所有可能排列結(jié)果，然后挨個遍歷，看是否在s2中

• 簡單粗暴
• 容易超時

---

思路2：滑動窗口

前提：abc排列結(jié)果集6種：[abc，acb，bca，bac，cab，cba]。但是無論怎么排列，6種結(jié)果集中，一定是根據(jù)元素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：每個字符出現(xiàn)的次數(shù)
• abc：（a-1，b-1，c-1）

mapSub2

• key：字符
• val：每個字符出現(xiàn)的次數(shù)
• bbb（b-3）

如果mapS1中的所有key集合
key - v1
key - v2
都滿足 v1 == v2，也就是說s1中的每個字符，都在sub2中，而且每個字符出現(xiàn)的頻率和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中每個元素，對應(yīng)的val值（出現(xiàn)頻率）都一樣。說明找到了！

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;}
}