跳到主要内容

回文串题库

题型一、回文子串​

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例1:

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例2:

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

方案A 中心扩展​

思路:

遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

遍历到数组的某一个元素时，以这个元素为中心，向两边进行扩展，如果两边的元素相同则继续扩展，否则停止扩展。

  • 处理回文串长度为奇数或者偶数的情况:

    1. 如果回文串长度为奇数: 回文中心是一个字符; 如果回文串长度为偶数: 回文中心是两个字符

    2. 长度为n的字符串会生成2n-1组回文中心[lefti,righti],其中

      • lefti=i/2;

      • righti=i/2+i%2

    3. 因此，只需要从0到2n-2遍历i，就可能得到所有可能的回文中心，这样就把奇偶情况统一了起来

function countSubstrings(s) {
    const len=s.length;
    let result=0;
    for(let i=0;i<2*len-1;i++){
        let left=Math.floor(i/2);
        let right=Math.floor(i/2)+i%2;
        while(left>=0&&right<len&&s[left]==s[right]){
            left--;
            right++;
            result++;
        }
    }
    return result;
};

性能分析:

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)

方案B、 Manacher 算法​

思路: 把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理 abba 这种偶数个字符的回文串。Manacher 法将所有的字符串全部变成奇数个字符

针对中心扩展算法的思想:

  • 由于回文串长度的奇偶性造成了不同性质的对称轴位置，中心扩展算法要对两种情况分别处理
  • 很多子串被重复多次访问，造成较差的时间效率

Manacher 算法怎么解决单双两次遍历的问题?

首先对字符串做一个预处理，在所有的空隙位置（包括首尾）插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的，并且回文串的中心不会是双数，以插入#号为例：

aba  ———>  #a#b#a#
abba ———>  #a#b#b#a#

Manacher 怎么解决重复访问的问题 ？ => 通过回文串的对称性，扩展回文串

字符:    #     a     #     b     #     a     #
RL :     1    2     1     4     1     2     1
RL-1:    0    1     0     3     0     1     0
位置:     0    1     2     3     4     5     6

字符:    #     a     #     b     #     b     #     a     #
RL :     1     2     1     2     5     2     1     2     1
RL-1:    0     1     0     1     4     1     0     1     0
位置:     0     1     2     3     4     5     6     7     8

  • 定义 r[i] : 表示以第 i 个字符为对称轴的回文串的回文半径。即r[i] 为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离

    • r[i] 最右回文字符位置下标：r[i]+i-1

  • 定义 rightMostIndex : 表示已访问到的最大回文子串的最右字符的位置下标

    • 若 r[i] 此时为最大回文子串的对称轴，那么 rightMost= r[i]+i-1

  • 定义 rightMostCenterIndex : 表示已访问到的最大回文子串的最右字符的对称轴所在位置下标

    • 若 r[i] 此时为最大回文子串的对称轴，那么 rightMostCenterIndex = i

  • 定义 maxR : 记录最大回文串的回文半径

    • 若 r[i] 此时最大，那么 maxR = r[i]

    • maxR-1 为 所求的最大回文串的长度

  • 定义 maxRCenterIndex : 记录最大回文串的对称轴所在位置下标

    • 若 r[i] 此时最大，那么 maxRCenterIndex=i

    • (maxRCenterIndex-maxR+1)/2 为 所求的最大回文串起始位置

所以 Manacher 关键点就是求 RL[i] 的问题

  • 当 i 在 rightMostIndex 的左边，由于回文串的特性

    • 根据此时 rightMostIndex 的对称轴 rightMostCenterIndex : j rightMostCenterIndex i , i 与 j 为对称关系

    • 此时要考虑 j 为对称轴时的回文长度 r[j] = r [2*rightMostCenterIndex-i]

      • 如果 r[j] 小，那么 r[i] 至少可能比 r[j] 大，那么 r[i]=r[j] ,因为 r[j] 有的 r[i] 肯定有

      • 如果 r[j] 大，那么 r[i] 和 r[j] 中肯定有一部分 rightMostIndex-i ,所以 r[i]=rightMostIndex-i

  • 当 i 在 rightMostIndex 的右边，说明没有任何一个以确认的回文串访问过，从紧挨着 i 的左右两边扩展

    • r[i]=1

综上所述保证了不会重复访问,然后就是以每一个字符为中心，进行左右扩展。并更新相应变量

function countSubstrings(s) {
    const len=s.length;
    let temp='';
    for(let i=0;i<len;i++){
        temp+='#';
        temp+=s.charAt(i);
    }
    temp+='#';
    let lenTemp=temp.length;
    let righMostIndex=0;
    let rightMostCenterIndex=0;
    let r=new Array(lenTemp);
    let result=0;
    for(let i=1;i<lenTemp;i++){
        if(i<righMostIndex){
            r[i]=Math.min(r[2*rightMostCenterIndex-i],righMostIndex-i);
        }else{
            r[i]=1;
        }
        while(i-r[i]>=0&&i+r[i]<lenTemp&&temp.charAt(i-r[i])==temp.charAt(i+r[i])){
            r[i]+=1;
        }
        if(r[i]+i-1>righMostIndex){
            righMostIndex=r[i]+i-1;
            rightMostCenterIndex=i
        }
        result+=Math.ceil((r[i]-1)/2);
    }
    return result;
};

性能分析:

  • 时间复杂度: O(n)
  • 空间复杂第: O(n)

题型二、段式回文​

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：

  • 每个 a_i 都是一个非空字符串；

  • 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；

  • 对于所有 1 <= i <= k，都有 a_i = a_{k+1 - i}。

示例1:

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例2:

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例3:

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

方案A、 双指针​

思路:

  1. 左边先走找到和右边指针相等的
  2. 然后右边递减判断相等是否能够覆盖到左指针此次开始的位置
  3. 如果覆盖到左边此次开始的位置表示可以划分为相同的段
  4. 如果不能覆盖，左边继续往右走，回到步骤1
function longestDecomposition(text) {
    let left=0;
    let right=text.length-1;
    let leftStart=0;
    let rightStart=text.length-1;
    let result=0;
    let k=0;
    while(left<right){
        while(left<right){
            if(text[left++]==text[right]){
                break;
            }
        }
        k=left--;
        while(left>=leftStart){
            if(text[right]!=text[left]){
                break;
            }
            left--;
            right--;
        }
        if(left<leftStart){
            result+=2;
            leftStart=k;
        }else{
            right=rightStart;
        }
        left=k;
        rightStart=right;
    }
    result=leftStart>rightStart?result:result+1;
    return result;
};

性能分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

题型三、最长回文子串​

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

示例1:

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

示例2:

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

示例3:

输入：s = "a"
输出："a"

示例4:

输入：s = "ac"
输出："a"

方案A、暴力破解法​

思路:

暴力法采用双指针两边夹，验证是否是回文子串。

原理就是对字符串从前到后依次进行遍历，最外层循环为子串头，第二层循环为确定子串尾，第三层循环为确定子串是否满足回文约束。

  • 定义双指针变量

    • 回文开始下标 start

    • 回文长度 maxLen 默认为 1 ，因为的单个字符都为回文串

  • 将字符串转换为数组，从前往后依次进行遍历。

    • 一层循环为回文串起始位置(最后一个字符不需要再遍历)
    • 二层循环为回文串截止位置
    • 三层循环为检验子串是否为回文串

  • 如果新的回文串长度 > 旧的回文串长度，更新回文开始下标和回文长度

    • 回文串长度 = 回文串截止位置 - 回文串开始位置 + 1
function isPalindrome(s,start,end){
    while(start<end){
        if(s.charAt(start++)!==s.charAt(end--)){
            return false
        }
    }
    return true
}
function longestPalindrome(s){
    let len=s.length;
    if(len<2){
        return s
    }
    let start=0;
    let maxLen=1;
    for(let i=0;i<len-1;i++){
        for(let j=i+1;j<len;j++){
            if(j-i+1>maxLen&&isPalindrome(s,i,j)){
                start=i;
                maxLen=j-i+1;
            }
        }
    }
    return s.substring(start,start+maxLen);
}

// const str = "babad"
// const str='cbbd';
const str='ac';
// const str='a';
console.log(longestPalindrome(str));

性能分析:

时间复杂度：O(N^3)，这里 N 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，都与 N 相关； 空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。

方案B、中心扩散 算法​

思路:

遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

遍历到数组的某一个元素时，以这个元素为中心，向两边进行扩展，如果两边的元素相同则继续扩展，否则停止扩展。

  • 定义双指针变量

    • 回文开始下标 start
    • 回文长度 maxLen 默认为 1 ，因为的单个字符都为回文串

  • 以每个字符为中心，依次向其左右进行扩展延伸获取回文串的长度

    • 一层 for 循环遍历每一个字符（作为中心）

      • 奇数中心 i
      • 偶数中心 i 和 i+1

    • 二层 for 循环向两边进行扩展，如果两边的元素相同则继续扩展，否则停止扩展

  • 无论是奇数中心扩散还是偶数中心扩散，得到的回文长度取最大值。如果这个这个最大值大于之前的 回文长度 ，更新回文长度与开始下标

    • 回文长度: 奇数中心或者偶数中心所得到的最大值
    • 回文开始下标: 奇数中心或者偶数中心 + （奇数中心或者偶数中心所得到的最大值-1）/2
function expand(s,left,right){
    while(left>=0&&right<s.length&&s[left]==s[right]){
        left--;
        right++;
    }
    return right-left-1
}
function longestPalindrome(s){
    let len=s.length;
    if(len<2){
    return s
    }
    let start=0;
    let maxLen=1;
    for(let i=0;i<len-1;i++){
        let odd=expand(s,i,i);
        let even=expand(s,i,i+1);
        let max=Math.max(odd,even);
        if(max>maxLen){
            maxLen=max;
            start=i-Math.floor((max-1)/2);
        }
    }
    return s.substring(start,start+maxLen);
}

const s = "babad";
// const s='cbbd';
// const s = 'ac';
// const s='a';
console.log(longestPalindrome(s));

性能分析:

时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n-1 个，每个回文中心最多会向外扩展 O(n) 次。

空间复杂度：O(1)。

方案C、动态规划 算法​

思路: 对暴力递归的优化

  • 确定状态方程: 当 j-i >=2 时 f[i][j] 是回文，那么 f[i+1][j-1] 一定是回文

    • f(i,j) = true , i=j （当 i = j 时，此时字符串由单个字符构成）

    • f(i,j) = S[i]=S[j] , j=i+1 (当 j=i+1 时，此时字符串由两个相同的字符构成)

    • f(i,j) = s[i]=s[j] and f(i+1,j-1) ,j>i+1

  • 定义双指针变量

    • 回文开始下标 start
    • 回文长度 maxLen 默认为 1 ，因为的单个字符都为回文串

  • 定义 dp

    • 如果 dp[left][right] = true ,说明字符串从 left 到 right 是回文字符串

    • 如果 dp[left][right] = false,说明字符串从 left 到 right 不是回文字符串

    • 根据状态方程与 dp （状态容器）得出状态方程为 : dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1] （从长度短的字符串长度向长度长的字符串转移）

  • 遍历 [left，right] 区间

    • left 与 right 范围: 0 < left < right 与 1< right <len

    • 如果 s.charAt(left)==s.charAt(right) && j-i+1<=3 说明此时为 aa 或者 aba ，更新dp[left][right]

    • 如果 s.charAt(left)==s.charAt(right) && dp[left+1][right-1]，更新 dp[left][right]

    • 如果 j-i+1 > maxLen 更新回文开始下标与回文长度

function longestPalindrome(s){
    let len=s.length;
    if(len<2){
        return s
    }
    let start=0;
    let maxLen=1;
    let dp=new Array(len).fill(0).map(value=>new Array(len).fill(false));
    for(let i=0;i<len;i++){
        dp[i][i]=true;
    }
    for(let j=1;j<len;j++){
        for(let i=0;i<j;i++){
            if(s[i]==s[j]&&((j-i+1)<=3||dp[i+1][j-1])){
                dp[i][j]=true;
                if(j-i+1>maxLen){
                    maxLen=j-i+1;
                    start=i;
                }
            }
        }
    }
    return s.substring(start,start+maxLen);
}

// const s = "babad";
// const s='cbbd';
// const s = 'ac';
const s='aa';
// const s='a';
console.log(longestPalindrome(s));

性能分析:

时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。

空间复杂度：O(n^2)，即存储动态规划状态需要的空间。

方案D、Manacher 算法​

思路: 把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理 abba 这种偶数个字符的回文串。Manacher 法将所有的字符串全部变成奇数个字符

针对中心扩展算法的思想:

  • 由于回文串长度的奇偶性造成了不同性质的对称轴位置，中心扩展算法要对两种情况分别处理
  • 很多子串被重复多次访问，造成较差的时间效率

Manacher 算法怎么解决单双两次遍历的问题?

首先对字符串做一个预处理，在所有的空隙位置（包括首尾）插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的，并且回文串的中心不会是双数，以插入#号为例：

aba  ———>  #a#b#a#
abba ———>  #a#b#b#a#

Manacher 怎么解决重复访问的问题？ => 通过回文串的对称性，扩展回文串

字符:    #     a     #     b     #     a     #
RL :     1    2     1     4     1     2     1
RL-1:    0    1     0     3     0     1     0
位置:     0    1     2     3     4     5     6

字符:    #     a     #     b     #     b     #     a     #
RL :     1     2     1     2     5     2     1     2     1
RL-1:    0     1     0     1     4     1     0     1     0
位置:     0     1     2     3     4     5     6     7     8

  • 定义 r[i] : 表示以第 i 个字符为对称轴的回文串的回文半径。即r[i] 为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离

    • r[i] 最右回文字符位置下标：r[i]+i-1

  • 定义 rightMostIndex : 表示已访问到的最大回文子串的最右字符的位置下标

    • 若 r[i] 此时为最大回文子串的对称轴，那么 rightMost= r[i]+i-1

  • 定义 rightMostCenterIndex : 表示已访问到的最大回文子串的最右字符的对称轴所在位置下标

    • 若 r[i] 此时为最大回文子串的对称轴，那么 rightMostCenterIndex = i

  • 定义 maxR : 记录最大回文串的回文半径

    • 若 r[i] 此时最大，那么 maxR = r[i]

    • maxR-1 为 所求的最大回文串的长度

  • 定义 maxRCenterIndex : 记录最大回文串的对称轴所在位置下标

    • 若 r[i] 此时最大，那么 maxRCenterIndex=i

    • (maxRCenterIndex-maxR+1)/2 为 所求的最大回文串起始位置

所以 Manacher 关键点就是求 RL[i] 的问题

  • 当 i 在 rightMostIndex 的左边，由于回文串的特性

    • 根据此时 rightMostIndex 的对称轴 rightMostCenterIndex : j rightMostCenterIndex i , i 与 j 为对称关系

    • 此时要考虑 j 为对称轴时的回文长度 r[j] = r [2*rightMostCenterIndex-i]

      • 如果 r[j] 小，那么 r[i] 至少可能比 r[j] 大，那么 r[i]=r[j] ,因为 r[j] 有的 r[i] 肯定有

      • 如果 r[j] 大，那么 r[i] 和 r[j] 中肯定有一部分 rightMostIndex-i ,所以 r[i]=rightMostIndex-i

  • 当 i 在 rightMostIndex 的右边，说明没有任何一个以确认的回文串访问过，从紧挨着 i 的左右两边扩展

    • r[i]=1

综上所述保证了不会重复访问,然后就是以每一个字符为中心，进行左右扩展。并更新相应变量

function longestPalindrome(s){
    let len=s.length;
    if(len<2){
        return s
    }
    let temp='';
    for(let i=0;i<len;i++){
        temp+='#';
        temp+=s.charAt(i);
    }
    temp+='#';
    let lenTemp=temp.length;
    let righMostIndex=0;
    let rightMostCenterIndex=0;
    let maxR=0;
    let maxRCenterIndex=0;
    let r=new Array(lenTemp);
    for(let i=0;i<lenTemp;i++){
        if(i<righMostIndex){
            r[i]=Math.min(r[2*rightMostCenterIndex-i],righMostIndex-i);
        }else{
            r[i]=1;
        }
        while(i-r[i]>=0&&i+r[i]<lenTemp&&temp.charAt(i-r[i])==temp.charAt(i+r[i])){
            r[i]+=1;
        }
        if(r[i]+i-1>righMostIndex){
            righMostIndex=r[i]+i-1;
            rightMostCenterIndex=i
        }
        if(r[i]>=maxR){
            maxR=r[i];
            maxRCenterIndex=i;
        }
    }
    return s.substring(Math.floor((maxRCenterIndex-maxR+1)/2),Math.floor((maxRCenterIndex-maxR+1)/2)+maxR-1);
}

const s = "babad";
// const s='cbbd';
// const s = 'ac';
// const s='aa';
// const s='a';
console.log(longestPalindrome(s));

性能分析:

时间复杂度：O(n)，其中 n 是字符串的长度。由于对于每个位置，扩展要么从当前的最右侧臂长 right 开始，要么只会进行一步，而 right 最多向前走 O(n) 步，因此算法的复杂度为 O(n)。

空间复杂度：O(n)，我们需要 O(n) 的空间记录每个位置的臂长。

题型四、分割回文串 II​

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例1:

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例2:

输入：s = "a"
输出：0

方案A、动态规划​

思路:

  • 第一次动态规划，将字符串 s 的每个子串是否为回文串预先计算出来
    1. 状态定义: dp1[i][j] 表示 s[i..j] 是否为回文串
    2. 状态转移方程:
      • 如果 i>=j 时，s[i,,j] 中仅有一个元素，则方程为:dp1[i][j]=true
      • 如果 i<j 时，s[i,,j] 中有两个及以上的元素，则方程为:dp1[i][j]=dp1[i+1][j-1]&&nums[i]==nums[j]
    3. 初始化状态: 单个字符都是回文串，即 dp1 中每个元素都是 true
  • 第二次动态规划

    1. 状态定义: dp2[i] 表示字符串的前缀 s[0..i] 的最少分割次数

    2. 状态转移方程:

      • 如果s[0,,,i] 本身为回文串，则方程为: dp2[i]=0 (s[0,,i] 本身为回文串，则不需要分割)
      • 如果s[0,,,i] 本身不为回文串且0<= j <i 时，有s[j+1,,i]为回文串，则方程为: dp2[i]=Math.min(dp2[i],dp2[j]+1)

    3. 状态初始化: dp2 中每一个元素初始无穷大

    4. 问题答案: dp2 中的最后一个元素即为答案

function minCut(s) {
    const len=s.length;
    const dp1=new Array(len).fill(0).map(value=>new Array(len).fill(true));
    for(let i=len-1;i>=0;i--){
        for(let j=i+1;j<len;j++){
            dp1[i][j]=s[i]==s[j]&&dp1[i+1][j-1];
        }
    }
    const dp2=new Array(len).fill(Infinity);
    for(let i=0;i<len;i++){
        if(dp1[0][i]){
            dp2[i]=0;
        }else{
            for(let j=0;j<i;j++){
                if(dp1[j+1][i]){
                    dp2[i]=Math.min(dp2[i],dp2[j]+1);
                }
            }
        }
    }
    return dp2[len-1]
};

性能分析:

题型五、验证是否为回文串​

回文字符串是一个正读和反读都一样的字符串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例2:

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

方案A、通过API​

将字符串分割后反转再拼接，看是否与原来的字符串相同

function isPalindromeString(str){
    if(!str||str.length<1){
        return false
    }
    return str.split('').reverse().join('')==str
}
let str='zwqhqwz';
console.log(isPalindromeString(str));

方案B、双指针-对撞指针​

用首尾两个指针，向中间扫描字符串，如果两指针指向的字符都一样， 这字符串就是一个回文。时间复杂度：O(n)，空间复杂度：O(1)

function isPalindrome(s) {
    let left=0;
    let right=s.length-1;
    while(left<right){
        while(left<right&&!/^[\da-zA-Z]+$/.test(s[left])){
            left++;
        }
        while(left<right&&!/^[\da-zA-Z]+$/.test(s[right])){
            right--
        }
        if(left<right){
            if(s[left].toLowerCase()!=s[right].toLowerCase()){
                return false
            }
            left++;
            right--;
        }
    }
    return true;
};

题型六、最长回文子序列​

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例1:

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例2:

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

方案A、动态规划​

思路: 对于一个子序列而言，如果它是回文子序列，并且长度大于 2，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

  1. 状态定义: dp[i][j] 表示字符串s的下标范围[i,j]内的最长回文子序列的长度。
  2. 状态转移方程:
    • 当0<=i<=j<len时，才会有dp[i][j]>0,否则dp[i][j]=0
    • 当i=j时，此时范围为[i,i] ,长度为i-i+1,由于任何长度为1的子序列都是回文子序列，则方程为:dp[i][i]=1
    • 当i<j时，计算dp[i][j]需要分别考虑s[i]和s[j]相等和不相等的情况
      • 如果s[i]=s[j]: 则首先得到s的下标范围[i+1,j-1]内的最长回文子序列，然后在子序列的首尾分别添加s[i]和s[j]，即可得到s的下标范围[i,j]内的最长回文子序列。方程为:dp[i][j]=dp[i+1][j-1]+2
      • 如果s[i]!=s[j]: 则s[i]和s[j]不可能同时作为同一个回文子序列的首尾。因此方程为:dp[i][j]=max(dp[i+1][j],dp[i][j-1])
  3. 初始化状态：
  4. 问题答案:
  5. 遍历循序: 由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，所以需要从后往前遍历。
function longestPalindromeSubseq(s) {
    const len=s.length;
    const dp=new Array(len).fill(0).map(()=>new Array(len).fill(0));
    for(let i=len-1;i>=0;i--){
        dp[i][i]=1;
        for(let j=i+1;j<len;j++){
            if(s[i]==s[j]){
                dp[i][j]=dp[i+1][j-1]+2;
            }else{
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }
    return dp[0][len-1];
};

性能分析:

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2)

题型七、判断一个链表是否为回文结构​

给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例:

1 2 3 3 2 1

方案A、快慢指针​

思路: 我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。整个流程可以分为以下五个步骤:

  1. 找到前半部分链表的尾节点, 我们可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。若链表有奇数个节点，则中间的节点应该看作是前半部分。

  2. 反转后半部分链表

  3. 判断是否回文

  4. 恢复链表

  5. 返回结果

实现

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
function endOfFirstHalf(head) {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}
function isPalindrome(head){
  if(head === null){
    return true;
  }
  const firstHalfEnd = endOfFirstHalf(head);
  const secondHalfStart = reverseList(firstHalfEnd.next);
  let p1 = head;
  let p2 = secondHalfStart;
  let result = true;
  while(result && p2 !== null){
    if(p1.val !== p2.val){
      result = false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
}