題目資訊

• 題目編號: 266
• 題目連結: Palindrome Permutation
• 主題: Hash Table, String, Bit Manipulation

題目敘述

給定一個字串 $s$，如果該字串的一個排列可以形成回文，返回 true，否則返回 false。

範例 1：

• 輸入： s = “code”
• 輸出： false

範例 2：

• 輸入： s = “aab”
• 輸出： true

範例 3：

• 輸入： s = “carerac”
• 輸出： true

限制條件：

• $1 \leq s.length \leq 5000$
• $s$ 僅由小寫英文字母組成。

直覺

判斷一個給定字串的任意排列是否可以形成回文的問題，主要圍繞在字串中字符的頻率。回文是一種兩邊對稱的結構，該字串正反皆可閱讀，因此每個字符在字串中的頻率應該理想上是偶數，以便能夠對稱排列。唯一的例外是，當回文串的長度為奇數時，可以允許有一個字符的頻率為奇數。因此，解決方案可以透過檢查字串中最多僅有一個字符具有奇數頻率來達成。

解法

提出的解法使用 bitset 來有效追蹤輸入字串中每個字符頻率的奇偶性。以下是此解法的逐步說明：

1. 初始化 bitset: 初始化一個大小為 26 的 bitset，對應於小寫的英文字母。bitset 中的每一位代表一個字符的頻率奇偶性（例如，被翻轉的位表示該字符當前具有奇數頻率）。

2. 迭代字串: 對字串中的每個字符，透過將字符減去 ‘a’ 計算其在 bitset 中的位置。翻轉該計算位置的位來更新該字符出現頻率的奇偶性。

3. 檢查奇偶性條件: 完成所有字符的處理後，檢查有多少位被設置（即，有多少字符具有奇數頻率）。為了使給定的字串具有形成回文的排列，在 bitset 中最多應只有一位被設置。這條件對應於允許一個字符具有奇數頻率，這在長度為奇數的回文中是允許的。

因此，通過驗證 bitset 條件，若最多只有一位被設置，則返回 true，否則返回 false。該方法有效地利用了位元操作，提供了 $O(n)$ 的時間複雜度，其中 $n$ 是字串的長度。

程式碼

C++

class Solution {
public:
    bool canPermutePalindrome(string s) {
        // 使用bitset來追蹤字元計數的奇偶性
        bitset<26> is_odd;
        
        // 遍歷字串中的每一個字元
        for (char c : s) {
            // 翻轉對應字元的位元
            is_odd.flip(c - 'a');
        }
        
        // 檢查是否最多只有一個字元的出現次數是奇數
        return (is_odd.count() < 2);
    }
};

Python

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # 使用集合來追蹤字元計數的奇偶性
        is_odd = set()
        
        # 遍歷字串中的每個字元
        for c in s:
            # 反轉每個字元對應的位元
            if c in is_odd:
                is_odd.remove(c)
            else:
                is_odd.add(c)
        
        # 檢查是否最多只有一個字元的計數是奇數
        return len(is_odd) < 2

複雜度分析

• 時間複雜度: $O(n)$

  演算法的時間複雜度是 $O(n)$，其中 $n$ 是輸入字串 $s$ 的長度。演算法在 for 迴圈中逐一遍歷字串中的每個字符，並翻轉 bitset 中對應的位元。bitset.flip() 和 bitset.count() 操作都在與字母表長度相關的常數時間 $O(1)$ 下運行（對於小寫英文字母來說是26），因此整體的時間複雜度由字串的遍歷決定。

• 空間複雜度: $O(1)$

  空間複雜度是 $O(1)$，因為用於記錄字符計數的 bitset 大小固定為26位元，無論輸入字串的大小為何。它不會隨著輸入字串 $s$ 的大小而變化，因此被認為是常數空間複雜度。