原题地址: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,然后两边的字符是相同的,比如 bb,从最简单的回文以 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] aba [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