給定兩個字串
s1和s2，判斷s2是否包含s1的排列（permutation）。換句話說，判斷s2的某個子字串是否是s1的 anagram。
Example:
Input: s1 = “ab”, s2 = “eidbaooo” Output: true
Intuition
TIP
用固定長度為 s1.length 的滑動視窗在 s2 上滑動，比較視窗內的字元頻率是否與 s1 相同。
- 排列的本質：兩個字串的字元頻率完全相同
- 用固定大小的視窗在
s2上滑動，每次檢查視窗內的字元頻率 - 可以用
matches計數器追蹤有多少個字元的頻率已經匹配，避免每次比較整個頻率陣列
Approaches
1. Sorting — O(n * m log m) / O(m)
- Idea: 對 s1 排序，再對 s2 的每個長度為
s1.length的子字串排序比較 - Time:
O(n * m log m)，n 為 s2 長度，m 為 s1 長度 - Space:
O(m)
Sorting Code
class Solution {
fun checkInclusion(s1: String, s2: String): Boolean {
if (s1.length > s2.length) return false
val sorted1 = s1.toCharArray().sorted()
for (i in 0..s2.length - s1.length) {
val sub = s2.substring(i, i + s1.length).toCharArray().sorted()
if (sub == sorted1) return true
}
return false
}
}⭐ 2. Sliding Window + Matches Counter — O(n) / O(1)
- Idea: 維護固定長度視窗，用 matches 計數器追蹤已匹配的字元種類數
- Time:
O(n)，n 為 s2 長度 - Space:
O(1)（固定 26 個字母）
class Solution {
fun checkInclusion(s1: String, s2: String): Boolean {
if (s1.length > s2.length) return false
val s1Count = IntArray(26)
val s2Count = IntArray(26)
for (i in s1.indices) {
s1Count[s1[i] - 'a']++
s2Count[s2[i] - 'a']++
}
var matches = 0
for (i in 0 until 26) {
if (s1Count[i] == s2Count[i]) matches++
}
for (right in s1.length until s2.length) {
if (matches == 26) return true
// 加入右邊字元
val rIdx = s2[right] - 'a'
s2Count[rIdx]++
if (s2Count[rIdx] == s1Count[rIdx]) matches++
else if (s2Count[rIdx] == s1Count[rIdx] + 1) matches--
// 移除左邊字元
val lIdx = s2[right - s1.length] - 'a'
s2Count[lIdx]--
if (s2Count[lIdx] == s1Count[lIdx]) matches++
else if (s2Count[lIdx] == s1Count[lIdx] - 1) matches--
}
return matches == 26
}
}🔑 Takeaways
- Pattern: 固定長度滑動視窗 + 頻率匹配
- Key trick: 用
matches計數器追蹤匹配的字元種類數，避免每次 O(26) 的比較，是 anagram 類問題的經典最佳化