69. 最长回文子串

day16: 5. 最长回文子串
（中等）

• 依旧暴力解法，没有通过所有的测试用例
• 中心扩散法：前面示例的慢的主要原因在于需要列举每种字符串组合的出现情况，循环次数等于（i*(i-1)/2）次，而下面的循环次数等于i次。
  使用中心扩散法，利用回文字串的特性,s[0]和s[n-1]位置的字符应该相同，不相同则判定不是回文字符串。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length == 1) return s;
  let max = 0,
    res = 0;
  let i = 0,
    j = 0;
  //遍历s，
  for (; i < s.length + 1; i++) {
    for (; j < s.length + 1; j++) {
      //截取i-j之间的元素
      if (j > i) {
        let temp = s.substring(i, j);
        //判断字符串是否是回文子串
        if (isPalind(temp)) {
          // max = Math.max(max, j - i);
          if (max < j - i) {
            max = j - i;
            res = i;
          }
        }
      }
    }
    j = 0;
  }
  console.log(i, j, max, res);
  return s.substring(res, res + max);
};

function isPalind(str) {
  //双指针
  str = [...str];
  let start = 0,
    end = str.length - 1;
  for (let i = 0; i < str.length - 1; i++) {
    while (start < end) {
      if (str[start] !== str[end]) {
        return false;
      } else {
        start++;
        end--;
      }
    }
  }
  return true;
}

longestPalindrome1 = function (s) {
  let len = s.length,
    max = 0,
    res = "";
  for (let i = 0; i < len; i++) {
    let r = i - 1,
      g = i + 1;
    //s[i]和右边相等，假设r左侧可能还有相同字符
    while (r >= 0 && s.charAt(r) == s.charAt(i)) {
      r--;
    }
    //s[i]和左边相等，假设g右侧可能还有相同字符
    while (g < len && s.charAt(g) == s.charAt(i)) {
      g++;
    }
    //左边和右边相等，说明在[r,g]范围内的为回文字符，假设g右侧可能还有相同字符，查找最大回文字串
    while (r >= 0 && g < len && s.charAt(r) == s.charAt(g)) {
      r--;
      g++;
    }
    //查找到最大的，修改max的值，并且标记坐标位置
    if (max < g - r - 1) {
      max = g - r - 1;
      res = s.substring(r + 1, g);
    }
  }
  return res;
};