214. Shortest Palindrome

给定一个字符串s，可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

问题等价于找到字符串从起始位置的最长回文子串，然后剩余部分的反转就是添加的字符串。

KMP（这个真的理解不了）

• 时间复杂度O(n)，空间复杂度O(n)
• Runtime: 80 ms, faster than 84.00%
• Memory Usage: 41.6 MB, less than 78.00%

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
  const n = s.length;
  const arr = new Array(n).fill(-1);
  for (let i = 1; i < n; i++) {
    let j = arr[i - 1];
    while (j !== -1 && s[j + 1] !== s[i]) {
      j = arr[j]
    }
    if (s[j + 1] === s[i]) {
      arr[i] = j + 1;
    }
  }
  
  let best = -1;
  for (let i = n - 1; i >= 0; i--) {
    while (best !== -1 && s[best + 1] !== s[i]) {
      best = arr[best];
    }
    if (s[best + 1] === s[i]) {
      best++;
    }
  }
 
  
  let add = (best === n - 1 ? '' : s.substr(best + 1, n));
  add = add.split('').reverse().join('');
  return add + s;
};

判断回文串

• 时间复杂度 O(n ^ 2)，空间复杂度O(1)
• but 超时了

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
  if (!s) return s;
  const len = s.length;
  for (let i = len; i > 0; i--) {
    if(isPalindrome(s.substring(0, i))) {
      return s.substring(i).split('').reverse().join('') + s;
    }
  }
};


var isPalindrome = function (s) {
  const len = s.length;
  for (let i = 0; i < len / 2; i++) {
    if (s[i] !== s[len - i - 1]) {
      return false;
    }
  }
  return true;
}