给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例 1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
提示:
由于是 s2
中判断是否包含 s1
的排列,而且 s1
和 s2
均为小数。
可以使用数组先对 s1
进行统计,之后使用滑动窗口进行扫描,每滑动一次检查窗口内的字符频率和 s1
是否相等 ~
以下代码,可以作为滑动窗口模板使用:
PS. 你会发现以下代码和 643. 子数组最大平均数 I 和 1423. 可获得的最大点数 代码很相似,因为是一套模板。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int m = s1.length(), n = s2.length();
if (m > n) return false;
int[] cnt = new int[26];
for (char c : s1.toCharArray()) cnt[c - 'a']++;
int[] cur = new int[26];
for (int i = 0; i < m; i++) cur[s2.charAt(i) - 'a']++;
if (check(cnt, cur)) return true;
for (int i = m; i < n; i++) {
cur[s2.charAt(i) - 'a']++;
cur[s2.charAt(i - m) - 'a']--;
if (check(cnt, cur)) return true;
}
return false;
}
boolean check(int[] cnt1, int[] cnt2) {
for (int i = 0; i < 26; i++) {
if (cnt1[i] != cnt2[i]) return false;
}
return true;
}
}
经过了前面几天的「滑动窗口」,相信你做这题已经很有感觉了。
这其实是某道困难题的简化版,本题根据「字符」滑动,而 30. 串联所有单词的子串 则是根据「单词」来。
但基本思路都是一样的,建议回顾~
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
「在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。」