題目敘述
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 10^4s1 and s2 consist of lowercase English letters.
題目翻譯
從 s2 中找出是否有包含 s1 的亂序組合。
解法解析
這題最好的解法就是用 Sliding window 的方式來解，可以使用陣列或 Hash Map 的方式來記錄字母的出現次數來做比對。因為是亂序的不需要記住順序。
簡單介紹 Sliding window 的方式。
s2：2 3 4 1 2 4 2 4
s1：4 1
Sliding window 就是一格一格的滑動過去。
- 先比對
s2 的 index 0 跟 1，亦即 2 3 跟 4 1 比對
- 然後再滑過去一格 index 1 跟 2，即 3 4 跟 4 1 比對
- 再滑一格 index 2 跟 3，4 1 跟 4 1 比對，找到了即答案
程式範例
Go
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
var s1Map = [26]int{}
var s2Map = [26]int{}
for i := 0; i < len(s1); i++ {
s1Map[s1[i]-'a']++
s2Map[s2[i]-'a']++
}
count := 0
for i := 0; i < 26; i++ {
if s1Map[i] == s2Map[i] {
count++
}
}
for i := 0; i < len(s2)-len(s1); i++ {
r := s2[i+len(s1)] - 'a'
l := s2[i] - 'a'
if count == 26 {
return true
}
s2Map[r]++
if s1Map[r] == s2Map[r] {
count++
} else if s1Map[r]+1 == s2Map[r] {
count--
}
s2Map[l]--
if s1Map[l] == s2Map[l] {
count++
} else if s1Map[l]-1 == s2Map[l] {
count--
}
}
return count == 26
}
JavaScript
var checkInclusion = function (s1, s2) {
if (s1.length > s2.length) return false;
const s1Map = new Array(26).fill(0);
const s2Map = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++) {
s1Map[s1[i].charCodeAt(0) - 97]++;
s2Map[s2[i].charCodeAt(0) - 97]++;
}
let count = 0;
for (let i = 0; i < 26; i++) {
if (s1Map[i] === s2Map[i]) {
count++;
}
}
for (let i = 0; i < s2.length - s1.length; i++) {
const r = s2[i + s1.length].charCodeAt(0) - 97;
const l = s2[i].charCodeAt(0) - 97;
if (count === 26) {
return true;
}
s2Map[r]++;
if (s1Map[r] === s2Map[r]) {
count++;
} else if (s1Map[r] + 1 === s2Map[r]) {
count--;
}
s2Map[l]--;
if (s1Map[l] === s2Map[l]) {
count++;
} else if (s1Map[l] - 1 === s2Map[l]) {
count--;
}
}
return count === 26;
};
Python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1map = [0] * 26
s2map = [0] * 26
for i in range(len(s1)):
s1map[ord(s1[i]) - ord('a')] += 1
s2map[ord(s2[i]) - ord('a')] += 1
count = 0
for i in range(26):
if s1map[i] == s2map[i]:
count += 1
for i in range(len(s2) - len(s1)):
r = ord(s2[i + len(s1)]) - ord('a')
l = ord(s2[i]) - ord('a')
if count == 26:
return True
s2map[r] += 1
if s2map[r] == s1map[r]:
count += 1
elif s2map[r] == s1map[r] + 1:
count -= 1
s2map[l] -= 1
if s2map[l] == s1map[l]:
count += 1
elif s2map[l] == s1map[l] - 1:
count -= 1
return count == 26
Reference
- https://github.com/Taiwolskit/leetcode/tree/master/Algorithms/567.%20Permutation%20in%20String