5 最长回文子串 | 中等级-算法

[OBKoro1]

博客链接

# 5 最长回文子串

# 题目链接

# 难度：中等

# 思路:

中心扩展法

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 代码：

双指针：中心扩展

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  let result = s[0] || "";
  // 遍历整个字符串
  for (let i = 0; i < s.length; i++) {
    // 选择一个中心点 j<=2尝试偶数和奇数两种形式的中心点
    for (let j = 1; j <= 2; j++) {
      // 对称回文或者中心点回文
      let left = i, // 左
        right = i + j; // 右
      // 当左右两遍的字符相同时 向外扩展直到两端不相同
      // 左右的边界
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--, right++; // 扩展
      }
      // 找到回文
      let length = right - left - 1; // (right - 1) - (left + 1) + 1
      // 对比 更新回文
      if (length > result.length) {
        result = s.substr(left + 1, length);
      }
    }
  }
  return result;
};

动态规划: 中心扩展

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length;
    let res = '';
    let dp = Array.from(new Array(n),() => new Array(n).fill(0));
    for(let i = n-1;i >= 0;i--){
        for(let j = i;j < n;j++){
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]);
            if(dp[i][j] && j - i +1 > res.length){
                res = s.substring(i,j+1);
            }
        }
    }
    return res;
};

# 鼓励我一下：

觉得还不错的话，给我的项目点个star吧

# 点个Star支持我一下~

博客链接