3 min read leetcode

438. Find All Anagrams in a String

438. Find All Anagrams in a String
Photo by Markus Spiske / Unsplash

題目連結: Find All Anagrams in a String

題目描述

給定兩個字串 s 和 p，找到 s 中所有是 p 的字母異位詞（Anagram）的子字串，返回這些子字串的起始索引。

  • 字母異位詞：兩個字串包含相同字母，且每個字母出現的次數相同，但順序可以不同。

限制條件

  • 1 <= s.length, p.length <= 3 * 10^4
  • s 和 p 只包含小寫英文字母

解題思路

為了找到所有是 p 的字母異位詞的子字串，我們可以使用滑動視窗（Sliding Window）的技巧，維持一個長度為 p.length 的視窗在字串 s 上滑動，並在滑動過程中檢查視窗內的子字串是否為 p 的字母異位詞。

具體步驟

  1. 建立目標字母頻率表：
    • 使用一個長度為 26 的整數陣列 need，記錄字串 p 中每個字母的出現次數。
  2. 初始化滑動視窗：
    • 使用另一個長度為 26 的整數陣列 window，記錄當前視窗內每個字母的出現次數。
  3. 滑動視窗遍歷 s：
    • 初始化視窗：
      • 將 s 的前 p.length 個字符加入 window 中。
      • 檢查 window 是否等於 need，若相等，則在答案中加入索引 0。
    • 開始滑動：
      • 從索引 p.length 開始，遍歷字串 s。
      • 每次移動視窗時：
        • 移除視窗最左邊的字符，更新 window。
        • 加入視窗右邊的新字符，更新 window。
        • 檢查 window 是否等於 need，若相等，則在答案中加入當前起始索引。
  4. 返回結果：
    • 最終返回所有符合條件的起始索引的列表。

測試範例說明

  • 範例 1：
    • s = "cbaebabacd", p = "abc"
    • 答案應為 [0, 6]。
      • 在索引 0 的子字串 "cba" 是 "abc" 的字母異位詞。
      • 在索引 6 的子字串 "bac" 是 "abc" 的字母異位詞。
  • 範例 2：
    • s = "abab", p = "ab"
    • 答案應為 [0, 1, 2]。
      • 在索引 0 的子字串 "ab" 是 "ab" 的字母異位詞。
      • 在索引 1 的子字串 "ba" 是 "ab" 的字母異位詞。
      • 在索引 2 的子字串 "ab" 是 "ab" 的字母異位詞。

程式碼

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (p.size() > s.size()) {
            return {};
        }

        vector<int> ans;
        unordered_map<char, int> m;
        for (const char ch : p) {
            m[ch] += 1;
        }

        int match = 0;
        for (int i = 0; i < p.size(); i += 1) {
            if (m.find(s[i]) != m.end()) {
                if (m[s[i]] > 0) {
                    match += 1;
                }
                m[s[i]] -= 1;
            }
        }

        if (match == p.size()) {
            ans.push_back(0);
        }

        for (int i = 0; i + p.size() < s.size(); i += 1 ) {
            if (m.find(s[i]) != m.end()) {
                if (m[s[i]] >= 0) {
                    match -= 1;
                }
                m[s[i]] += 1;
            }

            if (m.find(s[i + p.size()]) != m.end()) {
                if (m[s[i + p.size()]] > 0) {
                    match += 1;
                }
                m[s[i + p.size()]] -= 1;
            }

            if (match == p.size()) {
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};

時間與空間複雜度分析

  • 時間複雜度：O(n)，其中 n 是字串 s 的長度。
    • 分析：
      • 建立字母頻率表 need：O(m)，其中 m 是字串 p 的長度。
      • 初始化視窗 window：O(m)。
      • 滑動視窗遍歷 s：O(n - m)。
      • 比較兩個長度為 26 的陣列（window 和 need）：O(1)，因為陣列長度固定為 26。
      • 總時間複雜度為 O(n)。
  • 空間複雜度：O(1)。
    • 分析：
      • 使用了固定大小的陣列 need 和 window，大小為 26，與輸入大小無關。
      • 答案陣列 ans 最多包含 n 個元素，但題目要求返回所有符合條件的索引，這是必要的輸出空間。

Justin