原题地址：https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

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

示例1

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

示例2

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

构造输入

考虑到可能的场景，可以构造的输入如下，最后两个特别长的，是我在提交的时候发现的，也加上去了。

let str;

  • str = 'babad'; // 1
  • str = 'cbbd';
  • str = 'abb';
  • str = 'bbbb';
  • str = 'adam';
  • str = 'b';
  • str = 'bb';
  • str = '';
  • str = "kyyrjtdplseovzwjkykrjwhxquwxsfsorjiumvxjhjmgeueafubtonhlerrgsgohfosqssmizcuqryqomsipovhhodpfyudtusjhonlqabhxfahfcjqxyckycstcqwxvicwkjeuboerkmjshfgiglceycmycadpnvoeaurqatesivajoqdilynbcihnidbizwkuaoegmytopzdmvvoewvhebqzskseeubnretjgnmyjwwgcooytfojeuzcuyhsznbcaiqpwcyusyyywqmmvqzvvceylnuwcbxybhqpvjumzomnabrjgcfaabqmiotlfojnyuolostmtacbwmwlqdfkbfikusuqtupdwdrjwqmuudbcvtpieiwteqbeyfyqejglmxofdjksqmzeugwvuniaxdrunyunnqpbnfbgqemvamaxuhjbyzqmhalrprhnindrkbopwbwsjeqrmyqipnqvjqzpjalqyfvaavyhytetllzupxjwozdfpmjhjlrnitnjgapzrakcqahaqetwllaaiadalmxgvpawqpgecojxfvcgxsbrldktufdrogkogbltcezflyctklpqrjymqzyzmtlssnavzcquytcskcnjzzrytsvawkavzboncxlhqfiofuohehaygxidxsofhmhzygklliovnwqbwwiiyarxtoihvjkdrzqsnmhdtdlpckuayhtfyirnhkrhbrwkdymjrjklonyggqnxhfvtkqxoicakzsxmgczpwhpkzcntkcwhkdkxvfnjbvjjoumczjyvdgkfukfuldolqnauvoyhoheoqvpwoisniv";
  • str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

解题 - 暴力解法（无法通过）

任何题目的第一反应永远是暴力解法，如果使用暴力破解，首选的思路是遍历所有的字串，并且判断每个字串是否是回文。

这里两点比较重要：

  • 判断一个字串是不是回文，肯定是需要便利的，时间复杂度是 O(n)
  • 遍历所有的回文字串我采用的方式的时间复杂度是 O(n2)

上面两点看下来，最终的时间复杂度肯定是 O(n3)，而题目描述明确说了最大长度是 1000 ，生成所有字串的字串在 O(n2) 的时间复杂度上明显无法通过

不过还是给出一下暴力的代码吧（一开始我还想着用列表存储下所有的字串然后再遍历，简直是罪孽）：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
   return getAllSubString(s);
};

function getAllSubString(s) {
    const len = s.length;
    let res = '';
    for (let i = 0; i < len; i++) {
        let tmpStr = s[i];
        if(checkIsPalindromic(tmpStr) && res.length < tmpStr.length) {
            res = tmpStr;
        }
        for (let j = i + 1; j < len; j++) {
            tmpStr += s[j];
            if(checkIsPalindromic(tmpStr) && res.length < tmpStr.length) {
                res = tmpStr;
            } 
        }
    }
    return res;
}
// 判断是否是回文字串
function checkIsPalindromic(s) {
    let len = s.length;
    if (len === 1) return true;
    let index = Math.floor(len / 2);
    index = index % 2 !== 0 ? index : index - 1;
    for (let i = 0, j = len - 1; i < index, j >= index; i++ , j--) {
        if (s[i] !== s[j]) {
            return false;
        }
    }
    return true;
}

上面的代码没什么可取的地方，暴力的最大利好就是简单，判断回文串我不确定上面的方式是否是最优解，反正类似二分法去依次比较即可。

上面的解法处理全是 a 的输入，需要的时间是 648ms，这无疑是比较恐怖的，超时是必然的。

1.jpg

解题 - 动态规划解法

动态规划这玩意儿虚无缥缈，想当年被一个 0/1 背包问题都能虐的死去活来也没掌握真谛，有时候还不如贪心。

动态规划的精髓是局部最优全局最优

从上面的判断回文串的方法中可以发现，判断一个字符串是否是回文，需判断这个字符串是奇数长度还是偶数长度，不同的长度类型，回文串的判断方式自然不同。

现在利用动态规划的思想，我们需要先构造最简单的回文串，然后局部最优最终得到最长的回文串。

奇数长度的回文串

因此如果一个字符串是 babad`，我们很明显的能够知道以下几点：

  • a 是一个回文（同理 b 和 d 也是一个回文）
  • 既然已经知道 a 是回文，那么只要 a 前面的字符和 a 后面的字符相同，那么三个字符组成的字符串一定是回文

还是以 babad 举例，逻辑过程大致如下：

为了更直观的从代码层面去阐述这个过程，先说一下约定，

const s = 'babad';
let res = '';
for (let i = 0; i < s.length; i++) {
    let j = '';
    let tmpStr = '';
}

我们需要做的事情是：遍历 babad，最终的目的是得到类似 bab 这样的奇数长度的回文串，这种回文串最中间一定是有一个单独的字符，比如 a，然后两边的字符是相同的，比如 b和b，从最简单的回文以 a 为中心一直计算，直到不是回文串，我们得到的就是以 a 为中心的最长回文串。

  • 第1次遍历：i=0; j=1
s[i] = 'b';
s[i - j] = undefined; 
s[i + j] = 'a';
// 因为出现 undefined 说明无法继续遍历了，第一次遍历结束
  • 第2次遍历：i=1; j=1
// s = babad;
// i = 1; j = 1;
s[i] = s[1] = 'a';
s[i - j] = s[0] = 'b';
s[i + j] = s[2] = 'b';
s[i - j] = s[i + j];
tmpStr = 'bab';  // 得到一个回文串是 `bab`

注意，现在只是得到第一个以 a 为中心的回文字串，至于在 bab 的基础上是否存在更长的回文字串我们是不清楚的，因为我们需要在 i==0 的基础上继续遍历，此时变量 j 的作用就来了。

  • 第 2-2 次遍历：i=1;j=2
// s = babad;
// i = 1; j = 2;
// tmpStr = 'bab'
s[i - j] = undefined;
s[i + j] = s[3] = 'd';
// 不满足条件 第2次遍历结束
// tmpStr = 'bab'

每次 i 遍历结束，都需要和 res 结果比较，如果得到的回文串比 res 的结果长，则 res 使用新的 tmpSter，而在每次遍历开始的时候， tmpStr 需要把 s[i] 也就是最中间的字符赋值上去。

  • ... 其他遍历

从上面的解法可以归纳如下代码：

    for (let i = 0; i < len; i++) {
        let j = 1;
        let tmpStr= '';
        tmpStr= s[i];
        // 判断 ada 类型(奇数长度)回文
        while (s[i - j] === s[i + j] && s[i - j] && s[i + j]) {
            tmpStr= s[i - j] + tmpStr+ s[i + j];
            j++;
        }
        res = res.length > tmpStr.length ? res : tmpStr;
    }

偶数长度的回文串

得到奇数长度的最长回文串之后，就可以去计算偶数长度的最长回文字串。

偶数长度和奇数长度的唯一不同点在于，奇数长度比如 ada，中间一定是由一个字符 d，这个字符就是中心点。

而偶数长度的字符比较特殊，以 baab 举例，它是没有中间单独的字符的中心点，它的中心点是虚的。

如果要判断偶数长度的字符串是否是回文，就需要从 a [center] a 和 ba [center] ab 类似手动构造一个中心点去生成或者判断。

判断逻辑以 bbbb 举例：s = bbbb 偶数类型回文字串判断方式

注意在判断左右对称的时候，左边使用的是 s[i-j]，而右边使用的则是 s[i + j - 1]，因为没有中心字符，需要 -1<，也就是比较相邻的两个字符

  • 第一次遍历 // i = 0; j = 1;
continue; // 不具备判断条件
  • 第二次遍历 // i = 1; j = 1;
s[i - j] = s[0] = 'b';
s[i + j - 1] = s[1] = 'b';
tmpStr = 'bb';
  • 第 2-2 次遍历 //i = 1; j = 2;
//i = 1; j = 2;
s[i - j] = s[-1] = undefined;
continue;
  • 第3次遍历 // i = 2; j = 1
s[i - j] = s[1] = 'b';
s[i + j - 1] = s[2] = 'b';
tmpStr = 'bb';
  • 第3-2 次遍历 // i = 2; j = 2
s[i - j] = s[0] = 'b';
s[i + j - 1] = s[3] = 'd';
res = 'bb';

因此基本的代码逻辑可以这么实现：

// 判断 aaaa 类型(偶数长度)回文
j = 1;
while (s[i - j] === s[i + j - 1] && s[i - j] && s[i + j - 1]) {
    tmpStr2 = s[i - j] + tmpStr2 + s[i + j - 1];
    j++;
}

解题 - 完整代码

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    return getResult(s);
};

function getResult(s) {
    if (!s || s.length === 1) return s;
    const len = s.length;
    let res = s[0];
    for (let i = 0; i < len; i++) {
        let j = 1;
        let tmpStr1 = '';
        let tmpStr2 = '';
        if (s[i] === s[i + 1] && s[i + 1]) {
            const doubleStr = `${s[i]}${s[i + 1]}`;
            res = res.length > doubleStr.length ? res : doubleStr;
        }
        tmpStr1 = s[i];
        // 判断 ada 类型(奇数长度)回文
        while (s[i - j] === s[i + j] && s[i - j] && s[i + j]) {
            tmpStr1 = s[i - j] + tmpStr1 + s[i + j];
            j++;
        }
        // 判断 aaaa 类型(偶数长度)回文
        j = 1;
        while (s[i - j] === s[i + j - 1] && s[i - j] && s[i + j - 1]) {
            tmpStr2 = s[i - j] + tmpStr2 + s[i + j - 1];
            j++;
        }
        const tmpStr = tmpStr1.length > tmpStr2.length ? tmpStr1 : tmpStr2;
        res = res.length > tmpStr.length ? res : tmpStr;
    }
    return res;
}

结果

1.jpg

文章已经结束啦