判斷是否為迴文：詳解與實踐
在程式設計和演算法領域，「迴文」（Palindrome）是一個經常出現的概念。它指的是一個序列（通常是字串、數字或單詞）正讀和反讀都相同。例如，「aba」、「level」都是字串迴文，而「121」、「1331」則是數字迴文。判斷一個給定序列是否為迴文，是許多基本演算法練習的常見題目，同時也應用於某些資料處理和加密場景。
甚麼是迴文？
迴文的定義非常直觀：
- 字串迴文： 例如 "madam"、"racecar"、"上海自來水來自海上"。
- 數字迴文： 例如 121、1331、9009。
- 更廣泛的定義： 迴文的概念也可以擴展到其他序列，如數列、DNA序列等，只要其前後順序顛倒後仍然相同即可。
判斷迴文的基本思路
判斷一個序列是否為迴文，核心思想是比較序列的「前半部分」和「後半部分」是否一致。具體來說，我們可以有以下幾種常見的方法：
方法一：雙指標法
這是最常用且效率最高的方法之一。我們設定兩個指標，一個指向序列的開頭（左指標），另一個指向序列的末尾（右指標）。然後，我們逐步移動這兩個指標，同時比較它們所指向的元素。
- 初始化一個左指標 `left` 指向序列的第一個元素（索引為 0）。
- 初始化一個右指標 `right` 指向序列的最後一個元素（索引為 `length - 1`）。
- 當 `left` 小於 `right` 時，執行以下操作：
- 比較 `sequence[left]` 和 `sequence[right]`。
- 如果它們不相等，則該序列不是迴文，立即返回 `false`。
- 如果它們相等，則將 `left` 向右移動一位 (`left++`)，將 `right` 向左移動一位 (`right--`)。
- 如果迴圈結束（即 `left` 大於或等於 `right`），說明所有對應的元素都相等，該序列是迴文，返回 `true`。
優點： 時間複雜度為 O(n/2)，即 O(n)，空間複雜度為 O(1)，非常高效。
方法二：反轉序列法
另一種直觀的方法是將原始序列反轉，然後將反轉後的序列與原始序列進行比較。
- 創建一個新的序列，並將原始序列的元素按逆序複製到新序列中。
- 比較原始序列和新序列是否完全相同。
- 如果相同，則原始序列是迴文，返回 `true`。
- 如果不同，則原始序列不是迴文，返回 `false`。
對於字串： 可以直接使用語言提供的字串反轉函數，然後進行字串比較。
對於數字： 可以將數字轉換為字串，然後反轉字串進行比較。或者，通過數學運算反轉數字：每次取出數字的最後一位，然後乘以相應的權重累加到反轉數字中。
優點： 概念清晰，容易理解。
缺點： 可能需要額外的空間來存儲反轉後的序列（空間複雜度為 O(n)），或者在數字反轉時需要小心處理溢出問題。
方法三：遞迴法
迴文的結構也天然適合遞迴的解決方式。
- 基本情況 (Base Case)：
- 如果序列長度為 0 或 1，它總是迴文，返回 `true`。
- 遞迴步驟 (Recursive Step)：
- 比較序列的第一個元素和最後一個元素。
- 如果它們不相等，則該序列不是迴文，返回 `false`。
- 如果它們相等，則遞迴地判斷去除首尾元素後的「子序列」是否為迴文。
優點： 程式碼結構優雅，符合問題的遞迴定義。
缺點： 相較於迭代法，遞迴調用可能會有額外的函數呼叫開銷，空間複雜度通常為 O(n)（因為遞迴棧的深度）。
處理特殊情況
在判斷迴文時，還需要考慮一些特殊情況，特別是對於字串：
- 大小寫： "Racecar" 和 "racecar" 是否被視為迴文？通常，為了更靈活的判斷，我們會將所有字元轉換為統一的大小寫（例如，全部轉換為小寫）。
- 非字母數字字元： "A man, a plan, a canal: Panama" 這樣的句子，在忽略標點符號和空格後，是個迴文。因此，在判斷前，通常需要預處理字串，移除或忽略所有非字母數字字元。
字串預處理的步驟：
- 創建一個新的字串，或者使用一個字串生成器。
- 遍歷原始字串中的每個字元。
- 如果字元是字母或數字，則將其轉換為小寫，並添加到新的字串中。
- 然後，對這個預處理後的字串應用上述的迴文判斷方法（例如雙指標法）。
範例代碼（Python）
以下是使用雙指標法判斷字串是否為迴文的 Python 範例：
def is_palindrome_string(s: str) -> bool:
"""
判斷一個字串是否為迴文（忽略大小寫和非字母數字字元）。
"""
# 預處理字串：轉換為小寫，並只保留字母數字字元
processed_s = "".join(char.lower() for char in s if char.isalnum())
left, right = 0, len(processed_s) - 1
while left < right:
if processed_s[left] != processed_s[right]:
return False
left += 1
right -= 1
return True
# 測試範例
print(is_palindrome_string("A man, a plan, a canal: Panama")) # 輸出: True
print(is_palindrome_string("race a car")) # 輸出: False
print(is_palindrome_string("madam")) # 輸出: True
print(is_palindrome_string("hello")) # 輸出: False
以下是判斷數字是否為迴文的 Python 範例：
def is_palindrome_number(x: int) -> bool:
"""
判斷一個整數是否為迴文。
"""
# 負數不是迴文
if x < 0:
return False
# 個位數是迴文
if x < 10:
return True
# 如果數字的最後一位是0，則它不是迴文（除非數字本身就是0，但我們已經處理了）
if x % 10 == 0:
return False
reversed_number = 0
original_number = x
while x > reversed_number:
last_digit = x % 10
reversed_number = reversed_number * 10 + last_digit
x //= 10
# 對於奇數長度的數字，中間的數字不影響迴文判斷，可以通過 reversed_number // 10 來忽略
return original_number == reversed_number or original_number == reversed_number // 10
# 測試範例
print(is_palindrome_number(121)) # 輸出: True
print(is_palindrome_number(-121)) # 輸出: False
print(is_palindrome_number(10)) # 輸出: False
print(is_palindrome_number(12321)) # 輸出: True
print(is_palindrome_number(1221)) # 輸出: True
常見問題 (FAQ)
Q1: 如何在不創建額外字串的情況下判斷字串是否為迴文？
A1: 可以使用雙指標法。設定兩個指標，一個從字串開頭開始，一個從字串結尾開始，然後向中間移動，逐個比較對應位置的字元。這種方法的時間複雜度是 O(n)，空間複雜度是 O(1)。
Q2: 為什麼判斷數字迴文時，需要特別處理以 0 結尾的數字？
A2: 如果一個數字（大於 0）以 0 結尾，那麼它的反轉後的數字也必然以 0 開頭。一個非零數字的反轉後以 0 開頭是不可能的（除非原始數字本身就是 0），因此這樣的數字不可能是迴文（例如 120 反轉是 021，即 21，120 != 21）。唯一的例外是數字 0 本身，它是一個迴文。
Q3: 為什麼在處理字串迴文時，通常需要忽略大小寫和非字母數字字元？
A3: 這樣做是為了使迴文判斷更符合人類的理解和實際應用。例如，"Racecar" 和 "racecar" 在多數情況下應該被視為相同的迴文。同樣，像 "A man, a plan, a canal: Panama" 這樣的長句子，如果忽略標點和空格，它展現了迴文的結構，忽略這些非關鍵資訊可以讓我們發現更深層次的模式。
Q4: 遞迴方法在判斷迴文時有哪些潛在的問題？
A4: 遞迴方法雖然概念清晰，但在處理非常長的字串時，可能會導致堆疊溢出（Stack Overflow）錯誤，因為每次遞迴調用都會在調用堆疊上佔用空間。同時，遞迴調用的開銷也可能比迭代方法略高，使其在效能上不如雙指標法的迭代實現。
Q5: 如何高效地反轉一個數字？
A5: 可以使用迴圈來逐位提取數字的最後一位，然後將其加到一個反轉後的數字中。具體來說，每次從原數字中取最後一位 (`x % 10`)，然後將反轉數字乘以 10 加上這個最後一位 (`reversed_number = reversed_number * 10 + last_digit`)，最後將原數字除以 10 (`x //= 10`)。需要注意的是，在反轉過程中，要監測是否會發生整數溢出，特別是在使用固定位數的整數類型時。
