关于leetcode:leetcode-算法练习-5-最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。

• 示例 1：

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

• 示例 2：

输出：s = "cbbd"
输入："bb"

• 提醒：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法

本题我的项目地址

解题源代码

测试用例代码

暴力求解

• 判断是否是回文串

function isPalindrome(s: string): boolean {
  let l = 0;
  let r = s.length - 1;
  while (l < r) {if (s[l] === s[r]) {
      l++;
      r--;
    } else {return false;}
  }
  return true;
}

间接获取每个字符子串判断是否为回文串，最初输入最长子串

用数组保留回文子串，下标为长度，最初输入最初一个（比拟占内存）

export function longestPalindrome(s: string): string {const arr = [""];
  for (let i = 0; i < s.length; i++) {for (let j = i + 1; j <= s.length; j++) {const value = s.slice(i, j);
      if (isPalindrome(value)) {arr[value.length] = value;
      }
    }
  }
  return arr.pop()!;}

暴力求解的形式在字符串很长的时候就慢了一些，须要 17ms

• 优化

减少一个变量记录上一次的回文串长度，如果比之前的短就不做回文判断了

export function longestPalindrome(s: string): string {const arr = [""];
  let maxLen = 0;
  for (let i = 0; i < s.length; i++) {for (let j = i + 1; j <= s.length; j++) {const value = s.slice(i, j);
      if (j - i < maxLen) continue;
      if (isPalindrome(value)) {
        maxLen = value.length;
        arr[value.length] = value;
      }
    }
  }
  return arr.pop()!;}

优化过后快了一点，17ms 变成了 10ms，感知不是很强烈

然而如果 isPalindrome 的操作比较复杂的话，就会显著一些

咱们把 isPalindrome 的工夫拉长一点

function isPalindrome(s: string): boolean {const reverseStr = s.split("").reverse().join("");
  return s === reverseStr;
}

差距就呈现了，减少了变量缩小了判断，节俭了 isPalindrome 破费的工夫

核心扩散

以一个字符为中，向两边扩散，获取它右边一个字符和左边一个字符判断是否相等；相等则为回文串，持续扩散。

而后从第一个字符开始，查问出它的最大回文字符串，再与记录上一次子串比照，返回最长的子串；

须要两次 palindrome 是因为从一个字符扩散只蕴含了复数长度的回文串，因而还需减少两个字符为核心的扩散形式。

export function longestPalindrome(s: string): string {
  let res = "";

  for (let i = 0; i < s.length; i++) {
    // 复数回文串
    const s1 = palindrome(s, i, i);
    // 单数回文串
    const s2 = palindrome(s, i, i + 1);

    res = s1.length > res.length ? s1 : res;
    res = s2.length > res.length ? s2 : res;
  }

  function palindrome(s: string, l: number, r: number): string {while (l >= 0 && r < s.length && s.charAt(l) === s.charAt(r)) {
      l--;
      r++;
    }
    return s.substring(l + 1, r);
  }

  return res;
}

应用核心扩散的形式就快了很多，即便是优化过后的暴力求解，也拉开了很大的差距