字符串的排列(java实现)

力扣 567. 字符串的排列

题目说明

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

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

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

示例

例1

1
2
3

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

例2

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

笔者理解

此题是一道数组求解算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题比较直接，用滑动的窗口来存储s2中的一段字符串，然后比较窗口和s1中字母出现次数是否相等即可，

用一个大小26的数组当作字典来存储s1和s2窗口中字母出现的次数。

实现

public boolean checkInclusion(String s1, String s2) {
        int []dict = new int[26];
        //存储s1中各字母出现的次数
        int []contrast = new int[26];
        //存储s2中移动窗口各字母出现的次数
        for (int i = 0; i < s1.length(); i++) {
            dict[s1.charAt(i)-'a']++;
            //计算字母次数
        }
        for (int i = 0; i < s2.length(); i++) {
            contrast[s2.charAt(i)-'a']++;
            if(i>=s1.length()){
                //窗口移动，删去前端字母
                contrast[s2.charAt(i-s1.length())-'a']--;
            }
            if(Arrays.equals(dict,contrast)){
                //s1和s2窗口中的各字母出现次数相等
                return true;
            }
        }
        return false;
    }