problem

輸入為一個不為空的字串，回傳該字串是否為回文 (palindrome)。所謂回文是指從前到後和從後到前寫法一樣的字串，只有一個字元的字串也是回文。

sample input:
string = 'abcdcba'

sample output:
true

看到這題，會想到之前在 codewars 上看到很多字串題型的最熱門解法常常都是 '一行解'。

例如這題，可以寫成這樣：

function isPalindrome(string) {
  return string === string.split('').reverse().join('');
}

不太懂程式和演算法的時候，看到這種一行解會覺得好像很酷。但解的題越來越多之後，開始覺得這樣做有點不妙...以下第一種解的時間複雜度分析就是很好的原因。

solution 01

這題最直覺的解法就是直接將字串反轉，然後比較和原字串是否相同。步驟是：

1. 從尾端開始迴圈過字串的字元。
2. 將每個字元串接 (concatenate) 成一個新字串。或是將每個字元存進一個陣列，再合併陣列元素成一個新字串。
3. 比較原字串和新字串是否相同，回傳結果。

因為經過一次迴圈，然後存了一個同樣長度的新字串，所以很合理地會認為，若 n 為字串長度，這種解的時間複雜度為 O(n)，空間複雜度也是 O(n)。但是，但是！

字串串接的解法，時間複雜度其實是 O(n^2)。

// O(n^2) time | O(n) space
function isPalindrome(string) {
  let reversedString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    reversedString += string[i];
  }
  return string === reversedString;
}

陣列的解法，時間複雜度才是剛剛預期的 O(n)。

// O(n) time | O(n) space
function isPalindrome(string) {
  const reversedChars = [];
  for (let i = string.length - 1; i >= 0; i--) {
    reversedChars.push(string[i]);
  }
  return string === reversedChars.join('');
}

會有這樣的差異是在於，大部分程式語言中字串是不可變的 (immutable)，所以串接 (concatenation) 背後所做的其實是迴圈過字串的每個字元來創造出新的字串，也就是說每加上一個字元，就要迴圈過字串一遍，所以會需要 O(n^2) 時間。而在陣列中加入元素是常數時間操作，所以並沒有增加整體執行時間。

如果這兩種寫法都有這種細微差異，感覺用一行解就更不知道怎麼分析了。當然很多人寫一行解可能只是趣味或個人挑戰，並不真的用來分析討論，但這裡想記錄的是，理解演算法應該還是以 程式碼實作及有利於讀懂思維 為目標來減省程式碼比較理想。

solution 02

第二種解法使用遞迴。當一個字串為回文，其實也可以理解為字串的第一個字元會等於最後一個字元，而扣除掉頭尾這兩個字元，中間剩下的字串也會是回文。以此類堆，直到字串的中心，都會符合這樣的遞迴關係。
'abcdcba' → 'bcdcb'
'bcdcb' → 'cdc'
...

如果用虛擬碼，程式回傳的部分可以寫成：

return first == last AND isPalindrome(mid)

n 為字串長度
time: O(n)
space: O(n) 這是來自於遞迴中的堆疊，因為對每一個中間字串呼叫函式，呼叫 n/2 次，省略為 n。

函式帶入了第一個字元位置 i，並以此得出相對應的最後一個字元位置 j。在 i、j 不重疊的情況下，比較兩個字元，並對字串中間部分呼叫遞迴式。

function isPalindrome(string, i = 0) {
  const j = string.length - 1 - i;
  return i >= j ? true : string[i] === string[j] && isPalindrome(string, i + 1);
}

solution 03

最後一種方式使用迴圈，但利用了指標，就不用額外的空間儲存新字串。

步驟是：

1. 以兩個指標指向第一個及最後一個字元。
2. 比較兩個字元，若字元相等，則兩個指標向內移動，否則回傳 false。
3. 指標不重疊的情況下，重複步驟 2，最後回傳 true。

n 為字串長度
time: O(n)
space: O(1)

function isPalindrome(string) {
  let left = 0, right = string.length - 1;
  while (left < right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }
  return true;
}