LC567. 字符串的排列

题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 换句话说，s1 的排列之一是 s2 的 子串 。 示例 1： 输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 示例 2： 输入：s1= "ab" s2 = "eidboaoo" 输出：false 提示： 1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母

题目解析

题目在说什么

这道题其实是在问：能不能在 s2 里找到一个连续的片段，这个片段里的字母和 s1 的字母一模一样，只是顺序可以不同。

比如 s1 = "ab"，那么它的排列有 "ab" 和 "ba" 两种。我们要在 s2 = "eidbaooo" 里找有没有 "ab" 或 "ba" 这样的连续子串。结果发现 "ba" 出现在 s2 的第 4、5 个位置（从 0 开始数），所以返回 true。

如果 s2 里没有这样的连续片段，就返回 false。

思路是怎么来的

想象你有一盒字母积木（s1），你想知道在另一长串积木（s2）里，能不能找到一个长度相同的连续积木段，里面的字母种类和数量都和你手里的这盒一模一样，只是排列顺序可以打乱。

比如你手里有 1 个 'a' 和 1 个 'b'，那么只要在 s2 里找到一段连续的两个位置，里面恰好有一个 'a' 和一个 'b'（不管顺序），就算成功。

那怎么找呢？一个最笨的办法是：把 s2 里所有长度等于 s1 的连续片段都拿出来，检查每个片段里的字母种类和数量是否和 s1 相同。但这样太慢了。

聪明一点的办法是：滑动窗口。想象一个长度固定的“窗口”，它在 s2 上从左往右滑动。每次滑动时，窗口里会进来一个新字母，出去一个旧字母。我们只需要记录窗口里每个字母出现了几次，然后和 s1 的字母频次对比就行。

这就像你拿着一个“字母计数器”，一边走一边更新，而不是每次停下来重新数一遍。

代码逐步拆解

我们来看参考代码，把它拆开讲清楚。

第一步：准备两个计数器

int[] needs = new int[26];
for(char ch : s1.toCharArray()){
    needs[ch - 'a']++;
}

• needs 是一个长度为 26 的数组，用来记录 s1 里每个字母出现了几次。
• 因为题目说只有小写字母，所以用数组比用 HashMap 更快。
• ch - 'a' 是把字母转成 0~25 的数字，比如 'a' 对应 0，'b' 对应 1，这样就能用数组下标来记录频次。

int[] window = new int[26];

• window 用来记录当前滑动窗口里每个字母出现了几次。

第二步：滑动窗口

int start = 0;
for(int end = 0; end < s2.length(); end++){

• start 是窗口左边界，end 是右边界。窗口的范围是 [start, end]。
• 我们让 end 从 0 一直走到 s2 的末尾。

第三步：每次加入一个新字符

char cur = s2.charAt(end);
window[cur - 'a']++;

• 每次循环，end 指向的字符就是新进入窗口的字符。
• 我们在 window 数组里把这个字符的计数加 1。

第四步：检查当前窗口是否满足条件

if(isSame(window, needs)){
    return true;
}

• isSame 方法比较两个数组是否完全相等。如果相等，说明当前窗口里的字母种类和数量都和 s1 一模一样，那就找到了答案，直接返回 true。

第五步：保持窗口长度固定

if(end >= s1.length() - 1){
    char chr = s2.charAt(start);
    window[chr - 'a']--;
    start++;
}

• 窗口的长度应该始终等于 s1 的长度。
• 当 end 已经走到 s1 长度减 1 的位置时（也就是窗口已经填满了），之后每次右边界移动，左边界也要跟着移动，才能保持窗口长度不变。
• 具体做法是：把左边界指向的字符从 window 里减掉 1，然后左边界右移一位。