剑指 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.用两个hash表来存储两个字符串的字母的个数

2.看清楚题意,就是s2一个子区间内的所有字符数和s1的相同就行,我们一下就能想到滑动窗口了

3.用一个set去存储s1字符串其中的字母,能够给加速查找,就没必要26个字母都遍历一次了

4.简单的滑动窗口的实现

代码实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] hash1 =  new int[26];
        int[] hash2 =  new int[26];
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Set<Character> set = new HashSet<>();
        for(int i = 0;i<chars1.length;i++) {
            if(!set.contains(chars1[i])) set.add(chars1[i]);
            hash1[chars1[i]-'a']++;
        }
        int left=0,right = 0;
        while(right<chars2.length) {
            hash2[chars2[right]-'a']++;
            right++;
            if(right-left>=chars1.length) {
                if(isSub(set,hash1,hash2)) return true;
                else {
                    hash2[chars2[left]-'a']--;
                    left++;
                }
            }
        }
        return false;
    }
    public boolean isSub(Set<Character> set,int[] hash1,int[] hash2) {
        for(char c :set) {
            if(hash1[c-'a']!=hash2[c-'a']) return false;
        }
        return true;
    }
}

欢迎大佬们关注小弟的博客https://blog.csdn.net/qq_41522089