Leetcode 3 最长回文子串

题目描述

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

示例 1：

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

示例 2：

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

解法

方法一

暴力破解法，时间复杂为O(n^3)。

var longestPalindrome = function(s) {
  let max_len = 0;
  let max_str = '';
  const len = s.length;

  if (s == undefined || len === 1) return s;

  for (let i = 0; i < len; i++) {
    let max_len_of_current_str = 0;

    for (let j = 1; j <= len - i; j++) {
      const current_str = s.substr(i, j);

      const is_palindrome = check_is_palindrome(current_str);
      
      if (is_palindrome && j > max_len_of_current_str) {
        max_len_of_current_str = j;
      }
    }

    if (max_len < max_len_of_current_str) {
      max_len = max_len_of_current_str;
      max_str = s.substr(i, max_len_of_current_str);
    }
  }

  return max_str;
};

const check_is_palindrome = (s) => {
  const len = s.length;

  if (s == undefined || len < 1)  return false;

  let front = 0;
  let back = len -1;

  while (front < back) {
    if (s[front] !== s[back]) {
      return false;
    }

    front++;
    back--;
  }

  return true;
};

参考资料

• 回文判断
• 5. 最长回文子串