【力扣567】字符串的排列

题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：

1
2
3

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

示例 2：

1 2	输入：s1= "ab" s2 = "eidboaoo" 输出：false

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

实现代码

和【力扣76】最小覆盖字串思路一样，使用双指针的滑动窗口来实现

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

    int s1Len = s1.length(),s2Len = s2.length();
    if (s1Len > s2Len) {
      return false;
    }
    // 维护字符出现的次数
    int[] windowCount = new int[26];
    int[] subStrCount = new int[26];
    int left = 0, right = 0, n = 0, m = 0;
    for (char c : s1.toCharArray()) {
      if (subStrCount[c - 'a'] == 0) {
        m++;
      }
      subStrCount[c - 'a']++;
    }
    while (right < s2Len) {
      char c = s2.charAt(right);
      right++;
      if (subStrCount[c - 'a'] > 0) {
        windowCount[c - 'a']++;
        if (windowCount[c - 'a'] == subStrCount[c - 'a']) {
          n++;
        }
      }
      if ((right - left) == s1Len) {
        if (n == m) {
          return true;
        }
        char c1 = s2.charAt(left);
        if (subStrCount[c1 - 'a'] > 0) {
          if (windowCount[c1 - 'a'] == subStrCount[c1 - 'a']) {
            n--;
          }
          windowCount[c1 - 'a']--;
        }
        left++;
      }
    }
    return false;
  }
}

代码讲解

代码一

1
2
3

// 维护字符出现的次数
int[] windowCount = new int[26];
int[] subStrCount = new int[26];

和【力扣76】最小覆盖字串这道题思路不同的是这里通过两个数组维护字符串出现的次数；

为什么？

题目规定s1 和 s2 仅包含小写字母，也就是说最多26个字母，因为每个字母对应的ASCLL码都是有序的，比如a的ASCLL码是97，b是98，c是99……，如果将对应的字母减去a的ASCLL码值，就是数组对应的角下标，所以字符出现的次数就能维护在对应字母的数组角下标位置；

代码二

if ((right - left) == s1Len) {
  if (n == m) {
    return true;
  }
  char c1 = s2.charAt(left);
  if (subStrCount[c1 - 'a'] > 0) {
    if (windowCount[c1 - 'a'] == subStrCount[c1 - 'a']) {
      n--;
    }
    windowCount[c1 - 'a']--;
  }
  left++;
}