画解算法：5. 最长回文子串

2019-08-08 本文已影响0人 DeppWang

题目链接

https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解题方案

思路

标签：动态规划。
动态规划：通过子问题答案来解决大问题答案；子问题都需要是离散且不依赖其他子问题（详可见《算法图解》第九章「动态规划」）。
回文字符串：正读和反读都一样，""、"a"、"aa"、"aba"、"abcba" 等。
可将字符串 S 反转为 S'，通过 S 和 S' 比较，利用动态规划先得到 最长公共子串。
S 和 S' 分别置于横、纵坐标，通过网格（二维数组）一一比较子串（每一个子串就是一个子问题），当前公共子串的长度等于前面公共子串的长度加一，网格记录当前公共子串的长度。
通过最长公共子串的长度和结束位置，得到最长公共子串。
S = aacdecaa 和 S' = aacedcaa 最长公共子串为 acc，不是回文子串，需要进一步判断最长公共子串是否为回文子串。
caa 为 aac 的反向副本，通过检查反向子串 aac 的原始索引是否与子串 aac 索引相同，来排除反向副本的情况。
不需要检查反向子串 aac 的每个字符，只需要检查反向子串末尾字符 c 的原始索引，是否等于子串 aac 的首字符 a 索引即可。
时间复杂度：二维数组：O(n^2)。

代码 1：最长公共子串

class Solution {
    public String longestPalindrome(String s) {
        if (s.equals("")) {
            return "";
        }
        int length = s.length();
        String reversal = new StringBuffer(s).reverse().toString(); // 反转字符串
        int[][] cell = new int[length][length];
        int maxLen = 0; // 最长公共子串长度
        int maxEnd = 0; // 最长公共子串结束位置
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (reversal.charAt(i) == s.charAt(j)) {
                    if (i == 0 || j == 0) {
                        cell[i][j] = 1;
                    } else {
                        cell[i][j] = cell[i - 1][j - 1] + 1; // 公共子串长度
                    }
                } else {
                    cell[i][j] = 0;
                }
                if (cell[i][j] > maxLen) {
                    maxLen = cell[i][j];
                    maxEnd = j;
                }
            }
        }
        return s.substring(maxEnd + 1 - maxLen, maxEnd + 1);
    }
}

画解 1

1-1.png

2-1.png

3-1.png

代码 2：最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if (s.equals("")) {
            return "";
        }
        int length = s.length();
        String reversal = new StringBuffer(s).reverse().toString(); // 反转字符串
        int[][] cell = new int[length][length];
        int maxLen = 0; // 最长回文子串长度
        int maxEnd = 0; // 最长回文子串结束位置
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (reversal.charAt(i) == s.charAt(j)) {
                    if (i == 0 || j == 0) {
                        cell[i][j] = 1;
                    } else {
                        cell[i][j] = cell[i - 1][j - 1] + 1;
                    }
                }
                /**************修改的地方***************************/
                // 可为空，不用置为0，减少运行时间
//                else {
//                    cell[i][j] = 0;
//                }
                /**************************************************/
                if (cell[i][j] > maxLen) {
                    /**************修改的地方***************************/
                    int beforeIndex = length - 1 - i; // 反向子串末尾字符的原始索引
                    int firstIndex =  j - cell[i][j] + 1; // 子串的首字符索引
                    if (beforeIndex == firstIndex) { 
                        maxLen = cell[i][j];
                        maxEnd = j;
                    }
                    /**************************************************/
                }
            }
        }
        return s.substring(maxEnd + 1 - maxLen, maxEnd + 1);
    }
}