✅5. 最长回文子串

[bazinga-web]

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

[Ray-56]

var longestPalindrome = function(s) {
    // dp 解
    if (!s || !s.length) return '';
    let ret = s[0];
    const dp = []; // 二维数组

    for (let i = s.length; i >= 0; i--) { // 倒叙是因为 dp[i] 依赖于 dp[i + 1]
	    dp[i] = [];
	    for (let j = i; j < s.length; j++) {
		    // 特殊情况1：相等时为同一个字符
		    if (j === i) {
			    dp[i][j] = true;
		    } else if (j - i === 1 && s[j] === s[i]) { // 特殊情况2：只有两个的时候，是否相等
			    dp[i][j] = true;
		    } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
			    dp[i][j] = true;
		    }

		    // 当前为真，且长度大于已得到的长度 更新 ret
		    if (dp[i][j] && j - i + 1 > ret.length) {
			    ret = s.slice(i, j + 1);
		    }
	    }
    }

    return ret;
}

[bazinga-web]

/**

• 解题思路：
• 1. 如果字符串长度小于2，直接返回原字符串
• 2. 定义两个变量，一个start存储当前找到的最大回文子字符串的起始位置，第二个是maxLength记录字符串的长度 ,终止位置就是start+maxLength
• 3. 创建一个helper function，判断左右两边是否越界，同时左边字符是否等于右边字符，如果以上条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串起始位置。然后left--，right++，继续判断，直到不满足以上条件为止
• 4. 遍历字符串，每个位置调用helper function两遍，第一遍检查i-1，i+1（有中心点的情况）第二遍检查i，i+1（无中心点的情况）

*/

function longestPalindrome(s) {
  if (s.length < 2) {
    return s;
  }

  let start = 0;
  let maxLength = 1;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLength) {
        maxLength = right - left + 1;
        start = left;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i - 1, i + 1);
    expandAroundCenter(i, i + 1);
  }

  return s.substring(start, start + maxLength);
}