最长回文子序列

题目描述

最长回文子串

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

示例 1：

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

示例 2：

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

相关题目：最长回文子序列

解法一：

暴力匹配，从头开始匹配，其复杂度是O(n3)

解法二：

贪心解法，我们先认为答案串的长度是整个字符串的长度，然后根据这个这个长度在串中进行匹配。时间复杂度也是O(n3)。但是由于找到了首个串就是答案，所以比解法一快一点点。

解法三：

我们假设一个字符串中心（有可能是x，也有可能是xx），然后沿中心扩散，找到这个（或两个）字符为中心的最长回文子序列。其复杂度降到了O(n2)。

为什么会有降低复杂度的效果呢?这是由于我们利用了已经是回文子序列的串来寻找更长的串。这是一种很好的解题思路：利用子状态/子问题答案来扩展寻找答案。

class Solution {
    public String longestPalindrome(String s) {
        int ansIndex = 0, max = 0, pl = 0;
        boolean isEven = false;
        for (int i = 0; i < s.length(); i++) {
            pl = 0;
            for(int j = 0; j + i < s.length() && i - j >= 0; j++) {
                if(s.charAt(j + i) == s.charAt(i - j)) pl++;
                else break;
            }
            if(max < pl * 2 -1) {
                max = pl * 2 - 1;
                ansIndex = i;
            }
        }
        //稍微优化一下，这里其实可以直接从max/2开始
        for (int i = max / 2; i < s.length() - 1; i++) {
            if(s.charAt(i) == s.charAt(i + 1)) {
                pl = 1;
                for(int j = 1; i + j  + 1 < s.length() && i - j >= 0; j++) {
                    if(s.charAt(j + i + 1) == s.charAt(i - j)) pl++;
                    else break;
                }
                if(max < pl * 2) {
                    max = pl * 2;
                    ansIndex = i;
                    isEven = true;
                }
            }
        }
        if(isEven) {
            return s.substring(ansIndex - max / 2 + 1, ansIndex + max / 2 + 1);
        } else {
            return  s.substring(ansIndex - (max + 1) / 2 + 1, ansIndex + (max + 1) / 2);
        }
    }
}

其实这里还可以再优化一下。我们让解法三和配合上贪心算法，我们的扩散中心从最初的最左边，变成从最右边开始。这样我们更有机会得到更加长的回文子序列。（上面的写法，再leetcode上可以达到时间效率和空间效率双80%以上，再优化一下，可以更好）

解法四：

动态规划，这是更一般的利用子状态/子问题答案来扩展寻找答案的写法。我们得到这样的动态规划公式： dp[i][j]={dp[i+1][j−1]+2s[i]=s[j]0s[i]≠s[j]dp[i][j]= \begin{cases} dp[i+1][j-1]+2 & s[i]=s[j]\\ 0 & s[i] \ne s[j] \end{cases}dp[i][j]={dp[i+1][j−1]+20​s[i]=s[j]s[i]=s[j]​ 其中s是字符串。注意一下边界条件。

但这种动态规划其实没有必要，相比解法三，它浪费了更多的空间但时间复杂度相同。不过我们可以通过这种解法更深入的理解动态规划的核心思路。

解法五：

Manacher算法，专门解决这种字符串的子回文串的算法。

其核心思想是尽量利用已知的条件来降低后续的难度。算法的过程比较繁琐，不配图有点抽象，大家有兴趣可以自行了解一下。

这里给出代码(java代码，需要js,ts,c++代码的小伙伴可以留言我)：

class Solution {
    public String longestPalindrome(String s) {
        char[] str = new char[s.length() * 2 + 1];
        //填充str，为了让变成一个奇数
        for(int i = 0; i < s.length() * 2 + 1; i++) {
            if (i % 2 == 1) {
                str[i] = s.charAt(i / 2);
            } else {
                str[i] = '#';
            }
        }
        int[] f = new int[str.length];
        int  r = 0, index = 0;
        for (int i = 1; i < str.length; i++) {
            //如果当前的位置已经到了之前探索到的最边缘，就需通过这个位置向外扩展
            if(i >= r) {
                f[i] = (int) extend(i, 0, str);
                index = i;
                r = i + f[i];
            }
            else {
                //根据镜像的情况进行不同操作
                final int mir = index - (i - index);
                if(mir - f[mir] > index - f[index]) f[i] = f[index - (i - index)];
                else if(mir - f[mir] == index - f[index]) {
                    f[i] = (int) extend(i, f[mir], str);
                    index = i;
                    r = i + f[i];
                }
                else f[i] = mir - (index - f[index]);
            }
        }
        String ans = "";
        int ansNum = 0, ansIndex = 0;
        for(int i = 0; i < f.length; i++) {
            if(ansNum < f[i]) {
                ansNum = f[i];
                ansIndex = i;
            }
        }
        for (int i = ansIndex - ansNum; i <= ansIndex + ansNum; i++) {
            ans = ans + str[i];
        }
        return  ans.replace("#","");
    }
​
    /**
     *
     * @param pindex 当前位置
     * @param radius 从这个位置的半径多少开始匹配
     * @return 返回新的r
     */
    public Number extend(int pindex,int radius,char[] str) {
        radius++;
        while(pindex + radius < str.length && pindex - radius >= 0) {
            if(str[pindex + radius] == str[pindex - radius]) radius ++;
            else break;
        }
        return  radius - 1;
    }
}

“马拉车”算法的优势在于，这个算法充分的利用了已经匹配过的字符。上面的代码中，由于r(到达右边的最大距离)在扩展中是不会重复的，而除了扩展r带来的时间消耗，其他的时间消耗都为O(1)，所以整体的算法复杂度降低到了O(N)。