Day 09： Valid Palindrome

相信回文（palindrome）一定是在刚入门学习程序时一定会遇到的问题，
他虽然看起来很简单，但的确可以教我们很多演算法上的思维。
本篇会提供三种解法，一起来看从暴力法到优雅的解题的过程吧！

回文（palindrome）就是由前往後和由後往前念都像同的句子，像是'abcdcba'、'口罩罩口'...等等。

初学者一定有做过的方式，超直觉暴力法：

时间复杂度 : Ｏ(N^2) ，空间复杂度：Ｏ(N)

利用题目给你的字串反过来写一次，也就是先建一个空字串，把字一个个加(concat)上去，这个步骤其实会造成Ｏ(N^2)的时间复杂度，而後我们又要把建立好的结果和原本的字串来做比对

程序码会长得像下方⇊

function isPalindrome(string) {
  let reverseString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString += string[i];
  }
  return string === reverseString;
}

当然我们不能在这里就放过这一题，再想想有没有更好的做法？

如果一开始我们不建立一个空字串，建立一个空的阵列，我们用push的方式把加到array 相较一开的方式，这样只花Ｏ(N)

然後把新建的array.join()的方式变成字串和原本相比

function isPalindrome(string) {
  const reverseString = [];
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString.push(string[i]);
  }
  return string === reverseString.join('');
}

那有没有办法用递回（Recursion）的方式解决呢？

利用 return first === last and isPalindrome(middle)

但是Recursion的方式不一定有办法减少space

因为tail recursion依旧需要用到stack

程序码如下

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

那有没有办法减少空间复杂度？

当然可以！好用的pointer又派上用场了！

来看pointer的解法！

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

看完这写方式，Leetcode的题目指示加上一些变化，我们可以利用正则表达式

有关正则表达式，这里提供最近保哥线上提供的最新影片直播连接fb，有需要的可以再去观看！

下面提供解答参考拉！

var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]+/gim, '');
  s = s.toLowerCase();
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    if (s[start] !== s[end]) return false;
    start++;
    end--;
  }
  return true;
};