字符串的排列

字符串的排列

题目

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

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

示例1:

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

解题思路

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

    public boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int[] c1 = new int[26];
    int[] c2 = new int[26];
    
    for (char c : s1.toCharArray()) {
        c1[c - 'a']++;
    }
    
    for (int i = 0; i < len2; i++) {
        if (i >= len1)
            --c2[s2.charAt(i - len1) - 'a'];//先把坐标查过的减掉
        c2[s2.charAt(i) - 'a']++;
        if (Arrays.equals(c1, c2))
            return true;
    }
    
    return false;
    }