[LeetCode] JavaScript 解题 — 最长回文字串
原题地址: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
,这无疑是比较恐怖的,超时是必然的。
解题 - 动态规划解法
动态规划这玩意儿虚无缥缈,想当年被一个 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;
}
结果
文章版权:Postbird-There I am , in the world more exciting!
本文链接:http://www.ptbird.cn/leetcode-longest-palindromic-substring.html
转载请注明文章原始出处 !