题解 | #最长回文子串#

最长回文子串

http://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例1

输入：
"abc1234321ab",12

返回值：
7

思路一：扩展中心法

首先回顾一下什么事回文串：完全对称的字符串。

以上图为例，我想判断 acdcd ，最长的回文串，我可以找到某个点，然后以这个点为中心向两边扩散，如果两边的字符相等，说明两边之前是回文串；我在继续两两边扩散，知道不相等时停止，这样就找到了其中一个回文串。然后我在去试探以其他点为中心的回文子串，最终找到长度最长的就是答案。
这样一看是不是很简单，这下来用代码来描述上图的过程，在写代码之间还有一种情况要和大家讨论下：上图的回文串都是奇数个，那偶数个的回文串该咋判断那？其实也是运用中心法，只不过这个中心是两个字符而已，思想都是一样的。

AC 代码

public int getLongestPalindrome(String A, int n) {
        // write code here
        if (A == null || A.length() < 1) {
            return 0;
        }
        // 结果
        int res = 0;
        for (int i = 0; i < A.length(); i ++) {
            // 以 i 为中心，向两边扩散，针对奇数的回文串
            int len = cal(i, i, A);
            // 以 i 和 i + 1 为中心，向两边扩散，针对偶数的回文串
            int len1 = cal(i, i + 1, A);
            // 取上面两个最大值
            int len2 = Math.max(len, len1);
            // 和 res 比较，得出最大值
            res = Math.max(len2, res);
        }
        return res;

    }

    public int cal(int left, int right, String A) {
        // 当中心节点两边相等时，继续扩散
        while (left >= 0 && right < A.length() &&
           A.charAt(left) == A.charAt(right)) {
            left --;
            right ++;
        }

        return right - left - 1;
    }

时间复杂度：O(n^2)，n 为字符串长度。之所以是 n 的平方，首先是 n 个字符都会遍历一遍，然后每个字符最多会扩展 n 次。
空间复杂度：(n)，没有接触额外空间。

思路二：动态规划

在中心扩散法中其实做了很多重复计算，某个位置计算了很多次，咱们可以使用动态规划的方式将计算过的位置记录下来，用 dp[i][j] 来存储 i 和 j 之间是不是回文串。

AC 代码

public int getLongestPalindrome(String A, int n) {
        // write code here
        if (A == null || A.length() < 1) {
            return 0;
        }
        // 结果
        int res = 0;
        // 定义dp数组，用来存储计算过的结果
        boolean[][] dp = new boolean[n][n];
        // 枚举所有的组合
        for (int i = 1; i < A.length(); i ++) {
            for (int j = 0; j < i; j ++) {
                // 如果相等，并且位于中心两侧或dp[i - 1][j + 1]也是回文串
                if (A.charAt(i) == A.charAt(j) && (i - j <= 2 || 
                                                  dp[i - 1][j + 1])) {
                    // 那么本次两位也是回文串，记录到数组中
                    dp[i][j] = true;
                    // 计算最大值
                    res = Math.max(res, i - j + 1);
                }
            }
        }
        return res;

    }