leetcode 567. 字符串的排列(滑动窗口-java)

字符串的排列

难度 -中等
leetcode567. 字符串的排列

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

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

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

提示：
1 <= s1.length, s2.length <= 1e4
s1 和 s2 仅包含小写字母

滑动窗口

这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符。
题目要求 t 的排列之一是 s 的一个子串。而子串必须是连续的，所以要求的 s 子串的长度跟 t 长度必须相等。
那么我们有必要把 t 的每个排列都求出来吗？当然不用。如果字符串 a 是 b 的一个排列，那么当且仅当它们两者中的每个字符的个数都必须完全相等。
所以，根据上面两点分析，我们已经能确定这个题目可以使用 滑动窗口 + hash表 来解决。

我们使用一个长度和 t 长度相等的固定窗口大小的滑动窗口，在 s 上面从左向右滑动，判断 s 在滑动窗口内的每个字符出现的个数是否跟 t 每个字符出现次数完全相等。

我们定义 need是对 t 内字符出现的个数的统计，定义 wind是对 s 内字符出现的个数的统计。在窗口每次右移的时候，需要把右边新加入窗口的字符个数在 wind 中加 1，把左边移出窗口的字符的个数减 1。如果 need== wind，那么说明窗口内的子串是 t 的一个排列，返回 True；如果窗口已经把 s遍历完了仍然没有找到满足条件的排列，返回 False。

代码演示

 public boolean checkInclusion(String t, String s) {int n = t.length(), m = s.length();if (n > m) {return false;}HashMap<Character, Integer> need = new HashMap<>();HashMap<Character, Integer> wind = new HashMap<>();for (char c : t.toCharArray()){need.put(c,need.getOrDefault(c,0) + 1);}int left = 0;int right  = 0;int valid = 0;while (right < m){//右指针 向右移动 窗口扩大char c = s.charAt(right);right++;//判断新进来的字符 是否是需要的。if (need.containsKey(c)){wind.put(c,wind.getOrDefault(c,0) + 1);if (wind.get(c).equals(need.get(c))){valid++;}}//判断是否需要缩小窗口。while (right - left >= n){//找到直接返回trueif (valid == need.size()){return true;}//如何缩小窗口char d = s.charAt(left);left++;if (need.containsKey(d)){if (need.get(d).equals(wind.get(d))){valid--;}wind.put(d,wind.get(d) - 1);}}}return false;}

进阶优化版

这道题目中说明只有小写字母，因此我们可以用数组代替hash表，进行优化，数组代替hash表有两个好处，
1.优化了常数时间，数组的时间效率高于hash表，
2.优化了内存，数组更省空间，

代码演示：

  public boolean checkInclusion(String t, String s) {int n = t.length(), m = s.length();if (n > m) {return false;}int[] need = new int[26];int[] wind = new int[26];for (char c : t.toCharArray()){++need[c - 'a'];}int left = 0;int right  = 0;while (right < m){//右指针 向右移动 窗口扩大char c = s.charAt(right);right++;//判断新进来的字符 是否是需要的。if (need[c - 'a'] != 0){++wind[c - 'a'];}//判断是否需要缩小窗口。while (right - left >= n){//找到直接返回trueif (Arrays.equals(wind,need)){return true;}//如何缩小窗口char d = s.charAt(left);left++;if (need[d - 'a'] != 0){--wind[d - 'a'];}}}return false;}

上期经典

leetcode76. 最小覆盖子串