567. 字符串的排列
题目描述
输入两个字符串 s1 和 s2。
把 s1 的字符任意调换顺序可以得到它的各种排列。判断 s2 中是否有一段连续的子串，恰好是 s1 的某个排列，也就是说这段子串与 s1 长度相同，且每个字母出现的次数都一样。
存在则返回 true，否则返回 false。
示例 1
输入：s1 = "ab", s2 = "eidbaooo" 输出：true
解释：s2 中含有子串 "ba"，它是 "ab" 的一种排列。
示例 2
输入：s1 = "ab", s2 = "eidboaoo" 输出：false
解释：s2 中任意长度为 2 的连续片段都不是 "ab" 或 "ba"。
数据范围
1 <= s1.length, s2.length <= 10^4s1和s2只包含小写英文字母。
解题思路：定长滑动窗口
s1 的排列就是“字母次数与 s1 完全相同”的字符串，所以在 s2 上滑动一个长度固定为 m = len(s1) 的窗口。diff[c] = 窗口中 c 的次数 - s1 中 c 的次数，bad = diff 中不为 0 的字母个数。窗口右移时只有进来和出去的两个字母变化，在它们从 0 变非 0 或从非 0 变 0 时调整 bad。bad == 0 就找到了。
为什么正确
bad 始终等于当前窗口与 s1 在次数上不一致的字母种数。
复杂度分析
时间 O(m + n)，每步 O(1)；额外空间 O(26)。
易错点
s1 比 s2 长时要直接返回 false。另外不要忘记检查第一个窗口。更新 bad 时必须在修改前和修改后各判断一次是否为 0，这样进出是同一字母时也能正确抗消。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
diff = [0] * 26
for a, b in zip(s1, s2):
diff[ord(a) - 97] -= 1
diff[ord(b) - 97] += 1
bad = sum(1 for x in diff if x != 0)
if bad == 0:
return True
for i in range(m, n):
for c, d in ((s2[i], 1), (s2[i - m], -1)):
j = ord(c) - 97
if diff[j] == 0:
bad += 1
diff[j] += d
if diff[j] == 0:
bad -= 1
if bad == 0:
return True
return Falseclass Solution {
public boolean checkInclusion(String s1, String s2) {
int m = s1.length(), n = s2.length();
if (m > n) {
return false;
}
int[] diff = new int[26];
for (int i = 0; i < m; i++) {
diff[s1.charAt(i) - 'a']--;
diff[s2.charAt(i) - 'a']++;
}
int bad = 0;
for (int x : diff) if (x != 0) bad++;
if (bad == 0) {
return true;
}
for (int i = m; i < n; i++) {
char[] cs = {s2.charAt(i), s2.charAt(i - m)};
int[] ds = {1, -1};
for (int t = 0; t < 2; t++) {
int j = cs[t] - 'a';
if (diff[j] == 0) {
bad++;
}
diff[j] += ds[t];
if (diff[j] == 0) {
bad--;
}
}
if (bad == 0) {
return true;
}
}
return false;
}
}class Solution {
public:
bool checkInclusion(string s1, string s2) {
int m = s1.size(), n = s2.size();
if (m > n) {
return false;
}
vector<int> diff(26, 0);
for (int i = 0; i < m; i++) {
diff[s1[i] - 'a']--;
diff[s2[i] - 'a']++;
}
int bad = 0;
for (int x : diff) if (x != 0) bad++;
if (bad == 0) {
return true;
}
for (int i = m; i < n; i++) {
char cs[2] = {s2[i], s2[i - m]};
int ds[2] = {1, -1};
for (int t = 0; t < 2; t++) {
int j = cs[t] - 'a';
if (diff[j] == 0) {
bad++;
}
diff[j] += ds[t];
if (diff[j] == 0) {
bad--;
}
}
if (bad == 0) {
return true;
}
}
return false;
}
};func checkInclusion(s1 string, s2 string) bool {
m, n := len(s1), len(s2)
if m > n {
return false
}
diff := [26]int{}
for i := 0; i < m; i++ {
diff[s1[i]-'a']--
diff[s2[i]-'a']++
}
bad := 0
for _, x := range diff {
if x != 0 {
bad++
}
}
if bad == 0 {
return true
}
for i := m; i < n; i++ {
cs := [2]byte{s2[i], s2[i-m]}
ds := [2]int{1, -1}
for t := 0; t < 2; t++ {
j := cs[t] - 'a'
if diff[j] == 0 {
bad++
}
diff[j] += ds[t]
if diff[j] == 0 {
bad--
}
}
if bad == 0 {
return true
}
}
return false
}var checkInclusion = function(s1, s2) {
const m = s1.length, n = s2.length;
if (m > n) {
return false;
}
const diff = new Array(26).fill(0);
for (let i = 0; i < m; i++) {
diff[s1.charCodeAt(i) - 97]--;
diff[s2.charCodeAt(i) - 97]++;
}
let bad = diff.filter(x => x !== 0).length;
if (bad === 0) {
return true;
}
for (let i = m; i < n; i++) {
for (const [c, d] of [[s2.charCodeAt(i), 1], [s2.charCodeAt(i - m), -1]]) {
const j = c - 97;
if (diff[j] === 0) {
bad++;
}
diff[j] += d;
if (diff[j] === 0) {
bad--;
}
}
if (bad === 0) {
return true;
}
}
return false;
};function checkInclusion(s1: string, s2: string): boolean {
const m = s1.length, n = s2.length;
if (m > n) {
return false;
}
const diff = new Array<number>(26).fill(0);
for (let i = 0; i < m; i++) {
diff[s1.charCodeAt(i) - 97]--;
diff[s2.charCodeAt(i) - 97]++;
}
let bad = diff.filter(x => x !== 0).length;
if (bad === 0) {
return true;
}
for (let i = m; i < n; i++) {
for (const [c, d] of [[s2.charCodeAt(i), 1], [s2.charCodeAt(i - m), -1]]) {
const j = c - 97;
if (diff[j] === 0) {
bad++;
}
diff[j] += d;
if (diff[j] === 0) {
bad--;
}
}
if (bad === 0) {
return true;
}
}
return false;
}其他解法
定长窗口每步移入一个、移出一个字母并维护差异个数；变长窗口保证窗口内不超额，用长度判断是否匹配。两者都是线性时间。
解法 2：双指针（变长窗口） 时间 O(m + n)，空间 O(1)
cnt 先记为 s1 中各字母次数的相反数。右指针每加入一个字母 x 就把 cnt[x] 加一。若 cnt[x] > 0，不断右移左指针并把移出字母的计数减一，直到 cnt[x] 回到 0。这样窗口内每种字母都不超过 s1 中的次数，窗口长度等于 m 时就是一个排列。
不需要维护不同字母个数 bad，只看窗口长度。窗口长度可变，不变量是“没有字母超额”，理解上比定长窗口抽象一些。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
cnt = [0] * 26
for c in s1:
cnt[ord(c) - 97] -= 1
left = 0
for right in range(n):
x = ord(s2[right]) - 97
cnt[x] += 1
while cnt[x] > 0:
cnt[ord(s2[left]) - 97] -= 1
left += 1
if right - left + 1 == m:
return True
return Falseclass 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 left = 0;
for (int right = 0; right < n; right++) {
int x = s2.charAt(right) - 'a';
cnt[x]++;
while (cnt[x] > 0) {
cnt[s2.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == m) return true;
}
return false;
}
}class Solution {
public:
bool checkInclusion(string s1, string s2) {
int m = s1.size(), n = s2.size();
if (m > n) return false;
vector<int> cnt(26, 0);
for (char c : s1) cnt[c - 'a']--;
int left = 0;
for (int right = 0; right < n; right++) {
int x = s2[right] - 'a';
cnt[x]++;
while (cnt[x] > 0) {
cnt[s2[left] - 'a']--;
left++;
}
if (right - left + 1 == m) return true;
}
return false;
}
};func checkInclusion(s1 string, s2 string) bool {
m, n := len(s1), len(s2)
if m > n {
return false
}
cnt := [26]int{}
for i := 0; i < m; i++ {
cnt[s1[i]-'a']--
}
left := 0
for right := 0; right < n; right++ {
x := s2[right] - 'a'
cnt[x]++
for cnt[x] > 0 {
cnt[s2[left]-'a']--
left++
}
if right-left+1 == m {
return true
}
}
return false
}var checkInclusion = function(s1, s2) {
const m = s1.length, n = s2.length;
if (m > n) return false;
const cnt = new Array(26).fill(0);
for (const c of s1) cnt[c.charCodeAt(0) - 97]--;
let left = 0;
for (let right = 0; right < n; right++) {
const x = s2.charCodeAt(right) - 97;
cnt[x]++;
while (cnt[x] > 0) {
cnt[s2.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === m) return true;
}
return false;
};function checkInclusion(s1: string, s2: string): boolean {
const m = s1.length, n = s2.length;
if (m > n) return false;
const cnt = new Array(26).fill(0);
for (const c of s1) cnt[c.charCodeAt(0) - 97]--;
let left = 0;
for (let right = 0; right < n; right++) {
const x = s2.charCodeAt(right) - 97;
cnt[x]++;
while (cnt[x] > 0) {
cnt[s2.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === m) return true;
}
return false;
}