Day 10 ：Longest Palindromic Substring

不知道做完 Easy版本的Valid Palindrome看到这一题 Medium版Longest Palindromic Substring 的你有什麽想法？

一开始我看到这题的想法是：
我先把所有的Substring找出来，然後确认它是不是Palindrome後，存起来，并且用个空间纪录目前最长的答案。

於是我就来暴力Coding一下

function longestPalindromicSubstring(string) {
  let longest = '';
  for (let i = 0; i < string.length; i++) {
    for (let j = i; j < string.length; j++) {
      const substring = string.slice(i, j + 1);
      if (substring.length > longest.length && isPalindrome(substring)) {
        longest = substring;
      }
    }
  }
  return longest;
}

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;
}

不过，这个方法会花到Ｏ(n^3)，算是很糟糕的方式。
因为要找出Substring这件事我们就需要使用两次回圈，此外，所有的Substring都要去呼叫确认是否为palindrome的方法->isPalindrome(string)，也就是我们昨天实作出来的结果，它的时间复杂度是Ｏ(N)。

来想想有没有更好的做法。
先来观察一下Palindrome
'我爱你爱我'，假设今天这是在地板上的5个格子中的字，我们跳到第三格格子，发现往左右两边看都是"爱我"。
那如果今天是'我爱你你爱我'，我们一跳到第三格跟第四格中间的线上，发现往左右两边看都是"你爱我"。
有没有一点感觉了？
如果我们是一个裁判，我们只要在一个点上去计算我们左右两边看过去会是相同的长度，就可以知道这个Palindrome的长度是多少。可以分成：
在奇数长度时中心点会恰好是一个字

ab|c|ba
<-   ->

在偶数长度时中心会在线上

ab|ba
<- ->

利用这种方式，时间复杂度可以降到Ｏ(n^2)，因为我们每次都确认当下的字和前一个字的左右扩展，而每个扩展最多都花Ｏ(n)，而空间Ｏ(1)。

语法补充：

slice() 方法会回传一个新阵列物件，为原阵列选择之 begin 至 end（不含 end）部分的浅拷贝（shallow copy）。而原本的阵列将不会被修改。

参考: Array.prototype.slice()

最後把想法换成程序码吧！

var longestPalindrome = function (s) {
  let currentLongest = [0, 1];
  for (let i = 1; i < s.length; i++) {
    const odd = getLongestPalindrome(s, i - 1, i + 1);
    const even = getLongestPalindrome(s, i - 1, i);
    const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
    currentLongest = currentLongest[1] - currentLongest[0] > longest[1] - longest[0] ? currentLongest : longest;
  }
  return s.slice(currentLongest[0], currentLongest[1]);
};

function getLongestPalindrome(string, leftIndex, rightIndex) {
  while (leftIndex >= 0 && rightIndex < string.length) {
    if (string[leftIndex] != string[rightIndex]) break;
    rightIndex++;
    leftIndex--;
  }
  return [leftIndex + 1, rightIndex];
}

明日题目预告：
Subsets