LeetCode 567: Permutation in String

基本資料

#

難易度: medium 第一次嘗試： 2025-08-02

• 總花費時間：00:00.00

問題描述

#

給定兩個字符串 s1 和 s2，如果 s2 包含 s1 的排列，則返回 true，否則返回 false。換句話說，如果 s1 的某個排列是 s2 的子串，則返回 true。

解題思路

#

這道題與 LeetCode 438: Find All Anagrams in a String 非常相似。我們可以使用長度為26的陣列來存儲字符的出現次數，並在滑動窗口時匹配目標。關鍵區別是我們只需要找到一個匹配項而不是所有匹配項，所以我們可以在找到有效排列時立即返回 true。

解法

#

使用頻率陣列的滑動窗口

#

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        freq_s1 = [0] * 26
        freq_s2 = [0] * 26

        def get_ord_index(num):
            return ord(num) - 97

        # 初始化 s1 的頻率陣列
        for c in s1:
            idx = get_ord_index(c)
            freq_s1[idx] += 1

        # 在 s2 中滑動窗口
        for i in range(len(s2)):
            idx = get_ord_index(s2[i])
            freq_s2[idx] += 1

            # 移除落在窗口外的字符
            if i - len(s1) >= 0:
                idx = get_ord_index(s2[i - len(s1)])
                freq_s2[idx] -= 1

            # 檢查當前窗口是否匹配 s1 的頻率
            if freq_s2 == freq_s1:
                return True

        return False

演算法分析

#

時間複雜度

#

• 時間: O(n)，其中 n 是字符串 s2 的長度
• 空間: O(1)，因為我們使用固定大小的26元素陣列

關鍵優化

#

1. 早期返回: 我們在找到匹配項時立即返回 true，與 LeetCode 438 需要找到所有匹配項不同
2. 固定陣列大小: 使用陣列而不是雜湊表以獲得更好的性能
3. ASCII映射: 使用 ord(c) - 97 進行高效的字符到索引映射

收穫

#

1. 滑動窗口應用: 這道題展示了如何將滑動窗口技巧適應不同的需求 - 找到一個匹配項 vs. 找到所有匹配項。

2. 字符頻率比較: 對於已知字符集（小寫字母），使用固定大小陣列進行字符頻率計數比雜湊表更高效。

3. 優化機會: 與 LeetCode 438 不同，我們可以通過在找到第一個有效排列時立即返回來優化，使這道題在實踐中可能更快。

4. ASCII索引映射: ord(c) - 97 映射高效地將小寫字母轉換為陣列索引0-25，避免字典開銷。

5. 窗口管理: 滑動窗口維持固定大小等於 s1 的長度，確保我們只檢查可能包含排列的窗口。

6. 頻率陣列比較: 直接陣列比較 freq_s2 == freq_s1 比比較 Counter 對象或排序字符串更高效。

7. 邊界情況處理: 解決方案自然地處理 s2 比 s1 短的情況，通過永遠找不到匹配項。

8. 記憶體效率: O(1) 空間複雜度使這個解決方案對於大型輸入非常記憶體高效。

遇到的問題

#

1. 初始方法困惑: 我最初嘗試使用與 LeetCode 438 相同的方法，但必須適應它在找到第一個匹配項時立即返回，而不是收集所有匹配項。

2. 窗口大小管理: 確保窗口大小保持完全等於 s1 的長度至關重要。我必須仔細管理何時開始從頻率計數中移除字符。

3. 索引計算: 移除落在窗口外字符的計算 (i - len(s1)) 需要仔細注意以確保正確的窗口邊界。

4. 頻率陣列初始化: 我必須確保在開始滑動窗口過程之前正確初始化 s1 的頻率陣列。

5. 早期返回邏輯: 理解何時返回 true 很重要 - 我們需要在每次字符添加後檢查匹配項，而不僅僅是在最後。

6. 字符映射: 最初，我對ASCII映射感到困惑。理解小寫字母的ASCII值為97-122有助於澄清 ord(c) - 97 的計算。

關鍵要點

#

• 滑動窗口適應: 相同的技巧可以適應不同的問題需求
• 早期優化: 當只需要一個匹配項時，早期返回可以顯著提高性能
• 字符頻率陣列: 對於已知字符集，固定大小陣列比雜湊表更高效
• ASCII操作: 理解ASCII值有助於優化基於字符的演算法
• 窗口邊界管理: 仔細注意窗口邊界對於正確實現至關重要