首页 > itarticle > 字符串的排列

字符串的排列

admin 9月 30, 2020 0

题目

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:

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

示例2:

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

注意：

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

思路

这道题，我们用到的算法是滑动窗口，思路是这样的：
首先字符串s1的排列的可能性应该是它的长度的阶乘，因为字符串长度可能为10000，所以找出所有排列情况是不太可能。我们可以转换思路，不要关注排列的形式，而是关注排列中元素的数量关系，比如aab，那么，转换为数量关系就是{a:2,b:1}，因为S1长度为3，所以我们的窗口长度也为3，如果我们在S2的找到了这样一个窗口符合出现a的次数是两个，b是一个，那么S2就是包含S1的排列的。

解答

public boolean (String s1, String s2) {
    
    int l1 = s1.length();
    int l2 = s2.length();//字符串s2长度
    int[] c1 = new int[26];//用来存放字符串s1每个字符出现的次数
    int[] c2 = new int[26];//用来存放字符串s2每个字符出现的次数
    
     //把字符串s1转化成char数组，并计算每个字母对应的长度（注：a的ASCII码是 97）
    for(char c : s1.toCharArray())
        c1[c-'a']++;
        
    //循环遍历字符串s2截取与s1等长的字符数量去比较出现次数，当出现次数相同是直接返回true。
    //当出现次数不同时把循环下一组字符出现次数去比较。直到循环结束，没有相同的字符数量是返回false
    for(int i=0;i<l2;i++) 
    {
        //每当滑动窗口时，把没有覆盖的元素去除
        if(i>=l1) {
            char c = s2.charAt(i - l1);
            --c2[c-'a'];
        }
   
        c2[s2.charAt(i)-'a']++;
        //比较数组是否相同，也就是字符出现次数
        if(Arrays.equals(c1, c2))
            return true;
    }
    return false;
}