剑指 Offer II 014. 字符串中的变位词

---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20014.%20%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E5%8F%98%E4%BD%8D%E8%AF%8D/README.md

剑指 Offer II 014. 字符串中的变位词

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

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

 

示例 1：

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

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

 

提示：

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

 

注意：本题与主站 567 题相同： https://leetcode.cn/problems/permutation-in-string/

解法

方法一：滑动窗口

不妨记字符串 $s1$ 的长度为 $m$，字符串 $s2$ 的长度为 $n$。

我们观察发现，题目实际上等价于判断字符串 $s2$ 中是否存在窗口大小为 $m$，且窗口内的字符及其个数与字符串 $s1$ 相同的子串。

因此，我们先用哈希表或数组 $cnt1$ 统计字符串 $s1$ 中每个字符出现的次数，然后遍历字符串 $s2$，维护一个窗口大小为 $m$ 的滑动窗口，用哈希表或数组 $cnt2$ 统计窗口内每个字符出现的次数，当 $cnt1=cnt2$ 时，说明窗口内的字符及其个数与字符串 $s1$ 相同，返回 true 即可。

否则，遍历结束后，返回 false。

时间复杂度 $(m+n\times |\Sigma |)$，空间复杂度 $O(|\Sigma |)$。其中 $m$ 和 $n$ 分别为字符串 $s1$ 和 $s2$ 的长度；而 $|\Sigma |$ 为字符集的大小，本题中 $|\Sigma |=26$。

Python3

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:m, n = len(s1), len(s2)if m > n:return Falsecnt1 = Counter(s1)#前m字符cnt2 = Counter(s2[:m])if cnt1 == cnt2:return True#定长窗口for i in range(m, n):cnt2[s2[i]] += 1cnt2[s2[i - m]] -= 1if cnt1 == cnt2:return Truereturn False

Java

class Solution {public boolean checkInclusion(String s1, String s2) {int m = s1.length();int n = s2.length();if (m > n) {return false;}int[] cnt1 = new int[26];int[] cnt2 = new int[26];for (int i = 0; i < m; ++i) {++cnt1[s1.charAt(i) - 'a'];++cnt2[s2.charAt(i) - 'a'];}if (Arrays.equals(cnt1, cnt2)) {return true;}for (int i = m; i < n; ++i) {++cnt2[s2.charAt(i) - 'a'];--cnt2[s2.charAt(i - m) - 'a'];if (Arrays.equals(cnt1, cnt2)) {return true;}}return false;}
}

C++

class Solution {
public:bool checkInclusion(string s1, string s2) {int m = s1.size(), n = s2.size();if (m > n) {return false;}vector<int> cnt1(26), cnt2(26);for (int i = 0; i < m; ++i) {++cnt1[s1[i] - 'a'];++cnt2[s2[i] - 'a'];}if (cnt1 == cnt2) {return true;}for (int i = m; i < n; ++i) {++cnt2[s2[i] - 'a'];--cnt2[s2[i - m] - 'a'];if (cnt1 == cnt2) {return true;}}return false;}
};

Go

func checkInclusion(s1 string, s2 string) bool {m, n := len(s1), len(s2)if m > n {return false}var cnt1, cnt2 [26]intfor i := 0; i < m; i++ {cnt1[s1[i]-'a']++cnt2[s2[i]-'a']++}if cnt1 == cnt2 {return true}for i := m; i < n; i++ {cnt2[s2[i]-'a']++cnt2[s2[i-m]-'a']--if cnt1 == cnt2 {return true}}return false
}

TypeScript

function checkInclusion(s1: string, s2: string): boolean {const m = s1.length;const n = s2.length;if (m > n) {return false;}const cnt1 = new Array(26).fill(0);const cnt2 = new Array(26).fill(0);for (let i = 0; i < m; ++i) {++cnt1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)];++cnt2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)];}if (cnt1.toString() === cnt2.toString()) {return true;}for (let i = m; i < n; ++i) {++cnt2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)];--cnt2[s2[i - m].charCodeAt(0) - 'a'.charCodeAt(0)];if (cnt1.toString() === cnt2.toString()) {return true;}}return false;
}

方法二：滑动窗口优化

在方法一中，我们每次加入和移除一个字符时，都需要比较两个哈希表或数组，时间复杂度较高。我们可以维护一个变量 $diff$，表示两个大小为 $m$ 的字符串中，有多少种 字符出现的个数 不同。当 $diff=0$ 时，说明两个字符串中的字符个数相同。

时间复杂度 $O(m+n+|\Sigma |)$，空间复杂度 $O(|\Sigma |)$。其中 $m$ 和 $n$ 分别为字符串 $s1$ 和 $s2$ 的长度；而 $|\Sigma |$ 为字符集的大小，本题中 $|\Sigma |=26$。

Python3

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:m,n=len(s1),len(s2)if m>n:return False#初始化m窗口cnt=Counter()for a,b in zip(s1,s2[:m]):#例如，如果s1有字符a出现两次，s2前m个字符中的a出现一次，那么cnt[a]的值会是-1#（因为从s1的角度，它应该出现两次，而s2中出现一次，所以差异是-1）。cnt[a]-=1 #用s2去满足缺失cnt[b]+=1diff=sum(v!=0 for v in cnt.values()) if diff==0:return True #说明s2前m字符含字串#滑动定长窗口for i in range(m,n):a,b=s2[i-m],s2[i] #待删，待新增#根据移动之前cnt的情况，判断对diff的影响if cnt[a]==0:diff+=1if cnt[b]==0:diff+=1cnt[a]-=1cnt[b]+=1#根据移动之后cnt的情况，判断对diff的影响if cnt[a]==0:diff-=1if cnt[b]==0:diff-=1if diff==0:return Truereturn False

Java

class Solution {public boolean checkInclusion(String s1, String s2) {int m = s1.length();int n = s2.length();if (m > n) {return false;}int[] cnt = new int[26];for (int i = 0; i < m; ++i) {--cnt[s1.charAt(i) - 'a'];++cnt[s2.charAt(i) - 'a'];}int diff = 0;for (int x : cnt) {if (x != 0) {++diff;}}if (diff == 0) {return true;}for (int i = m; i < n; ++i) {int a = s2.charAt(i - m) - 'a';int b = s2.charAt(i) - 'a';if (cnt[a] == 0) {++diff;}--cnt[a];if (cnt[a] == 0) {--diff;}if (cnt[b] == 0) {++diff;}++cnt[b];if (cnt[b] == 0) {--diff;}if (diff == 0) {return true;}}return false;}
}

C++

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);for (int i = 0; i < m; ++i) {--cnt[s1[i] - 'a'];++cnt[s2[i] - 'a'];}int diff = 0;for (int x : cnt) {if (x != 0) {++diff;}}if (diff == 0) {return true;}for (int i = m; i < n; ++i) {int a = s2[i - m] - 'a';int b = s2[i] - 'a';if (cnt[a] == 0) {++diff;}--cnt[a];if (cnt[a] == 0) {--diff;}if (cnt[b] == 0) {++diff;}++cnt[b];if (cnt[b] == 0) {--diff;}if (diff == 0) {return true;}}return false;}
};

Go

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']--cnt[s2[i]-'a']++}diff := 0for _, x := range cnt {if x != 0 {diff++}}if diff == 0 {return true}for i := m; i < n; i++ {a, b := s2[i-m]-'a', s2[i]-'a'if cnt[a] == 0 {diff++}cnt[a]--if cnt[a] == 0 {diff--}if cnt[b] == 0 {diff++}cnt[b]++if cnt[b] == 0 {diff--}if diff == 0 {return true}}return false
}

TypeScript

function checkInclusion(s1: string, s2: string): boolean {const m = s1.length;const n = s2.length;if (m > n) {return false;}const cnt: number[] = new Array(26).fill(0);for (let i = 0; i < m; ++i) {--cnt[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)];++cnt[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)];}let diff = 0;for (const x of cnt) {if (x !== 0) {++diff;}}if (diff === 0) {return true;}for (let i = m; i < n; ++i) {const a = s2[i - m].charCodeAt(0) - 'a'.charCodeAt(0);const b = s2[i].charCodeAt(0) - 'a'.charCodeAt(0);if (cnt[a] === 0) {++diff;}if (--cnt[a] === 0) {--diff;}if (cnt[b] === 0) {++diff;}if (++cnt[b] === 0) {--diff;}if (diff === 0) {return true;}}return false;
}

Swift

class Solution {func checkInclusion(_ s1: String, _ s2: String) -> Bool {let m = s1.countlet n = s2.countif m > n {return false}var cnt1 = [Int](repeating: 0, count: 26)var cnt2 = [Int](repeating: 0, count: 26)let aAscii = Character("a").asciiValue!for i in 0..<m {cnt1[Int(s1[s1.index(s1.startIndex, offsetBy: i)].asciiValue! - aAscii)] += 1cnt2[Int(s2[s2.index(s2.startIndex, offsetBy: i)].asciiValue! - aAscii)] += 1}if cnt1 == cnt2 {return true}for i in m..<n {cnt2[Int(s2[s2.index(s2.startIndex, offsetBy: i)].asciiValue! - aAscii)] += 1cnt2[Int(s2[s2.index(s2.startIndex, offsetBy: i - m)].asciiValue! - aAscii)] -= 1if cnt1 == cnt2 {return true}}return false}
}