猫猫说了算
理解是偶然,误解是常态。

【算法】查找一个字符串中的最长回文子串

远浅发表于: 2021-07-30 11:20分类: 技术

5. 最长回文子串

遍历每一个字符串,从这个字符往两边查找,然后贪心找出最长的回文字符串

/**
 * @description
 * 给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  if (s.length < 2) return s;

  let res = "";

  const dfs = (left, right) => {
    while (left >= 0 && right < s.length && s[left] == s[right]) {
      left--;
      right++;
    }
    // 判断本轮回文字符串长度是否大于之前一轮的回文字符串
    // left 0, right 1;
    // 长度是 2 right - left +1
    // 本轮实际的实际长度是  (right-1)-(left+1)+1
    if (right - left - 1 > res.length) {
      res = s.slice(left + 1, right);
    }
  };

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

  return res;
};

console.log(longestPalindrome("babad"), longestPalindrome("cbbd"));

赠人玫瑰, 手有余香。🌹
打赏
特别鸣谢
感谢以下用户对本文的支持与鼓励
加载打赏用户中
发表评论
文章评论
暂无任何评论,快去发表吧~