Open sisterAn opened 3 years ago
第 1 步:定义状态
dp[i][j]
表示子串 s[i..j]
是否为回文子串,这里子串 s[i..j]
定义为左闭右闭区间,可以取到 s[i]
和 s[j]
。
第 2 步:思考状态转移方程
对于一个子串而言,如果它是回文串,那么在它的首尾增加一个相同字符,它仍然是个回文串
dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]
第 3 步:初始状态:
dp[i][i] = true // 单个字符是回文串
if(s[i] === s[i+1]) dp[i][i+1] = true // 连续两个相同字符是回文串
代码实现:
const longestPalindrome = (s) => {
if (s.length < 2) return s
// res: 最长回文子串
let res = s[0], dp = []
for (let i = 0; i < s.length; i++) {
dp[i][i] = true
}
for (let j = 1; j < s.length; j++) {
for (let i = 0; i < j; i++) {
if (j - i === 1 && s[i] === s[j]) {
dp[i][j] = true
} else if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true
}
// 获取当前最长回文子串
if (dp[i][j] && j - i + 1 > res.length) {
res = s.substring(i, j + 1)
}
}
}
return res
}
复杂度分析:
dp初始化有问题吧,第一轮循环就会报错
中心扩散法
function fn(str) {
if(!str.length) return ''
let res = str[0]
const setRes = (j, k) => {
if(str[j] !== str[k]) return
while (str[j]&&str[j] === str[k]&&str[k]) {
res = res.length >= j - k + 1 ? res : str.slice(k, j + 1)
j++
k--
}
}
for (let i = 1, len = str.length; i < len; i++){
setRes(i,i-1)
setRes(i,i-2)
}
return res
}
动态规划法
function longestPalindrome(s: string): string {
// 字符串长度小于 2 返回
if (s.length < 2) {
return s;
}
// dp[i][j] 即字符串 s 下标从 i 到 j 是否为回文字符串。
const dp: boolean[][] = [];
// 默认子串为第一个字符, 即 dp[0][0]
let res = s[0];
for (let j = 1; j < s.length; j ++) {
for (let i = 0; i <= j; i ++) {
// 如果 dp[i] 未初始化,初始化为空数组。
if (dp[i] === undefined) {
dp[i] = [];
}
// 回文子串的长度
const l = (j - i) + 1;
// 首尾两个字符是否相等
dp[i][j] = (s[i] === s[j]);
// 如果长度小于等于 3,即 a, aa, aba, 首尾两个字符相等即该子串 i ~ j 是否是回文字符串
// 大于 3 的情况下,判断首尾及上一轮比较情况,即 abcdcba, 即判断 a 和 a && b 和 b, 其中 b 和 b 的值又来自于 c 和 c, 依此类推
if (l >= 4) {
dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1];
}
// 如果是回文字符串且长度大于之前,重新赋值
if (dp[i][j] && l > res.length) {
res = s.substring(i, j + 1);
}
}
}
return res;
};
console.log(longestPalindrome("aacabdkacaa"));
> function longestPalindrome(str) {
let arr = []
let fun = function (s) {
for (let i = 0; i < s.length; i++) {
let v = s[i]
//查找 剩下字符中相同字符
let index = s.substring(i + 1, s.length).indexOf(v)
//存在
if (index > -1) {
arr.push(s.substring(i, index + 2))
}
//循环
fun(s.substring(i + 1))
}
}
fun(str)
}
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
示例 2:
leetcode