剑指 Offer II 014. 字符串中的变位词

题目

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

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

示例 1：

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

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

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

分析

难点：
1、怎么巧妙的使用双指针
2、怎么去理解这两个循环
3、怎么去判断多个字符串的（就是第一个循环）
4、第二个循环的下标位和循环的起止条件

  // 视频：左吃右拉的概念{https://www.bilibili.com/video/BV15S4y177Zc?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c}
    // 使用双指针（滑动窗口）+hash表
    public boolean checkInclusion(String s1, String s2) {
        // 边界判断
        if(s1.length() > s2.length()){
            return false;
        }
        // 定义一个列表存储值（存储s1）
        int[] counts = new int[26];
        for(int i=0; i<s1.length(); i++){
            // 这里就开始将双指针的思想用起来
            counts[s1.charAt(i)-'a']++;
            counts[s2.charAt(i)-'a']--;
        }
        if(allZero(counts)){
            return true;
        }
        // 开始迭代判断(定位到后面的指针，也方便循环结束判断)
        for(int j=s1.length(); j<s2.length(); j++){
            counts[s2.charAt(j)-'a']--;
            // 因为上面对s2前面的值进行了--
            counts[s2.charAt(j-s1.length())-'a']++;
            if(allZero(counts)){
                return true;
            }
        }
        return false;
    }

    private boolean allZero(int[] counts){
        for(int count:counts){
            if(count != 0){
                return false;
            }
        }
        return true;
    }
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