LeetCode：567. 字符串的排列（java）

一开始以为只是简单的找子串，结果，是找子串的排列，我能想到的是暴力解法，也算是变相的滑动窗口，只是我是用HashMap来记录s1的（单）词频，官方解题是用数组。我觉得这题的关键点在通过比较字母数量来判断是否为子串的排列。【由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。】话不多说，直接上解题思路和代码！

以下是三种解题方式：

采用双循环，外层循环是窗口移动，内层循环是大小为n1(即s1的长度）的窗口。用HashMap来记录词频。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 1.暴力解法，双循环。借助HashMap，比较字母数量来判断是否为子串排列——时间复杂度和空间复杂度都高
        HashMap map=new HashMap<>();
        int n1=s1.length();
        int n2=s2.length();
        char c;
        HashMap copy;
        if(n1>n2) return false;     // 条件判断
        for(int i=0;i)map.clone();
            for(;j0)
                    copy.put(c,v-1);
                else
                    break;
            }
            if(j==i+n1)
                return true;
        }
        return false;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {

        // 3.滑动窗口：用两个数组cnt1和cnt2分别统计s1的字母数量和s2中窗口大小为n1的字母数量是否相等
        int n1=s1.length();
        int n2=s2.length();
        int[] cnt1=new int[26];
        int[] cnt2=new int[26];
        if(n1>n2)   return false;
        for(int i=0;i

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 4.双指针，让cnt用s1初始化，然后根据cnt[i]是否小于0，找到长度为n的子串
        int n1=s1.length();
        int n2=s2.length();
        int[] cnt=new int[26];
        int start=0,end=0;
        for(int i=0;i0){ //start指针右移到end
                cnt[s2.charAt(start)-'a']--;
                start++;
            }
            if(end-start+1==n1)  return true;
        }
        return false;
    }
}