[演算法題目] Palindrome Check / Valid Palindrome

本題資訊

難度：easy
使用語言：C++
相關概念：Strings

---

題目敘述

Write a function that takes in a non-empty string and that returns a boolean representing whether the string is a palindrome.
A palindrome is defined as a string that’s written the same forward and backward. Note that single-character strings are palindromes.

這題要求檢查一個字串是否為回文，回文意思是不論從前面讀或從後面讀都一樣。

Input: abcdcba

Output: true

這題概念蠻簡單的，而我剛拿到題目是簡化版的，只有小寫且沒有標點符號，所以處理上又更簡單。但我在查資料時發現實際上這題應該是要能判斷真實的一句話的，例如很著名的：”A man, a plan, a canal: Panama!”，因此我會寫兩個，一個是簡化版的一個是比較完整的。

Idea 1

這裡先分析簡化版的。

比較直線思考的模式是把字串從最後一個開始，一個一個放去新的空間裡面，再逐一比對兩個字串是不是一樣，但空間上要花費 \(O(n)\)，而像這種只要回傳 true 或 false 的題目，如果等級較簡單的話，最好企圖能夠直接判斷回傳。

另一個直線思考的作法是一個 index 從開頭開始，另外一個 index 從尾端開始，使用兩個迴圈逐一比對。時間複雜度將會來到 \(O(n^2)\)，但我們知道字串長度，且透過兩端逼近，完全可以省一個迴圈達到 \(O(n)\)，還不用花到其他空間。

using namespace std;

bool isPalindrome(string str) {
  int i = 0;
  int j = str.size() - 1;
  
  while (i <= j){
    if (str[i] != str[j])
      return false; //只要有不符合的，直接回傳false，不需要完全比對完。
    i++;
    j--;
  }
  return true;
}

時間複雜度：\(O(n)\)，\(n\) 是指 str 長度。
空間複雜度：\(O(1)\)

另外我看到很酷的寫法分享給大家，但我對這個用法不熟，一時之間很難想到：

using namespace std;

bool isPalindrome(string str) {
  return equal(str.begin(), str.end(), str.rbegin());
}

Idea 2

這裡是完整寫法。

其實就只是多一步，因為有 Idea 1 為基礎了，我想就直接處理原字串，把標點符號或空格等等非字母和數字刪除，並且將所有字母改成小寫。

這裡我處理方式是用正規表達式，因為先前剛好有複習到這一塊，就在這裡試試看。刪掉非英數字後，在兩邊逼近時轉換字母的大小寫進行比對，比對的邏輯和 Idea 1 的做法差不多。

#include <iostream>
#include <regex>
using namespace std;

bool isPalindrome(string str) {
  regex reg("[^a-zA-Z0-9]");
  str = regex_replace(str, reg, "");
  int i = 0;
  int j = str.size() - 1;
  
  while (i <= j){
    if (tolower(str[i]) != tolower(str[j]))
      return false;
    i++;
    j--;
  }
  return true;
}

不過時間上非常非常慢XD 應該是正規表達式的關係，所以我打算改成用 ASCII code 判斷大小寫和數字，若非大小寫範圍直接跳過，一樣兩端逼近比對。

（這裡之後補上）