567. 字符串的排列(一般)

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例 1：

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

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string

思路：

滑动窗口，类比438

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public boolean checkInclusion(String s1, String s2) {

        //滑动窗口
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        //统计t中各元素个数
        //for(int i =0 ;i<t.length();i++){
        //    Character key = t.charAt(i);
        //    need.put(key,need.getOrDefault(key,0)+1);
        //}
        for(char c : s1.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        //开始定义窗口双指针
        int left =0,right=0;
        int count = 0;//这个用来记录
        List<Integer> res = new ArrayList<>();
        while(right<s2.length()){
            //获取移入窗口的值
            char c = s2.charAt(right);
            right++;
            //窗口更新
            //如果移入的值在所需的字符串中
            if(need.containsKey(c)){
                //窗口+1
                window.put(c,window.getOrDefault(c,0)+1);
                //如果需要的个数正好满足
                if(window.get(c).equals(need.get(c))){
                    count++;
                }
            }
            //确定左边是否要收缩
            while (right-left>=s1.length()){

                //判断长度是否可以更新
                if(count==need.size()){
                    //需要记录一下开始的索引
                    return true;
                }
                //移动左边，窗口缩小
                char c1 = s2.charAt(left);
                left++;
                //开始更新窗口内容
                //如果当前要移动的字符是包含在need中，我们需要进行讨论，如果该字符的次数刚好与我们需要的次数相等，则valid--，并同时更新window中这个值出现的次数
                if(need.containsKey(c1)){
                    //左边有重复的
                    if(window.get(c1).equals(need.get(c1))){
                        count--;
                    }
                    window.put(c1,window.getOrDefault(c1,0)-1);
                }
            }
        }
        //返回
        return false;
    }
}