算法题--最长回文子串

给定一个字符串，求该字符串中的最长回文子串。

> 回文：正着读和反着读完全一样的字符串，例如：a，aa，aba，abba，

例如，给定字符串ababcba，它的回文子串有：aba、bab、abcba，其中最长回文子串是abcba。

#### 一、暴力求解法：

思路：

两个指针代表子串的左右端点，判断子串是否回文，回文的话判断是否是最大的。

注意：有个小优化的点就是判断的时候，用max记录已经判断过的最长回文子串的长度，判断时可以先判断子串长度是不是比max大，如果不是的话也没必要判断是否回文了。

代码：

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/14
 * Class description: 最长回文子串
 * 1、暴力解法（两边向内扩散）
 * 2、中心扩散法
 * 3、动态规划
 * 4、马拉车
 */
public class MaxPalindrome {
    public static void main(String[] args) {
        String str = "ababcba";
//        String str = "abc";

String result = violence(str);
        System.out.println(result);
    }

/**
     * 暴力解法
     * @param str
     * @return
     */
    public static String violence(String str) {
        //特殊情况处理:null、""和1个字符
        if (str == null) {
            throw new RuntimeException("字符串不能为null");
        }
        if (str.length() <= 1) {
            return str;
        }

//记录起始索引值，和最长回文子串的长度
        //这里maxLen要初始化为1，因为即使没有回文子串，单个字符串也是回文子串，最小长度为1
        int startIndex = 0, maxLen = 1;
        //validPalindrome方法内要用，这里直接定义一下，不用每次都获取了
        char[] charStr = str.toCharArray();
        //依次判断str的每个子串，看是否为回文：定义两个游标，分别为子串的左边界和右边界
        //左端点到倒数第二位就可以了，右端点到倒数第一位
        for (int i = 0; i < str.length() - 1; i++) {
            for (int j = i + 1; j < str.length(); j++) {
                int currentStrLen = j - i + 1;
                //验证是否为最长回文子串：先验证长度是否为最长，不是的话，就不需要验证是否为回文了
                //这里不需要切割，直接传入子串的左右边界(索引值)更方便
                if (currentStrLen > maxLen && validPalindrome(charStr, i, j)) {
                    startIndex = i;
                    maxLen = currentStrLen;
                }
            }
        }
        return str.substring(startIndex, startIndex + maxLen);
    }

/**
     * 验证指定子串是否为回文串
     * @param charStr 字符串转换的字符数组
     * @param left 左边界
     * @param right 右边界
     * @return 是否为回文串
     */
    private static boolean validPalindrome(char[] charStr, int left, int right) {
        while (left < right) {
            if (charStr[left] != charStr[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```

#### 二、中心扩散法：

思路：

上面暴力解法是从两边向中间判断，也可以从中间向两边扩散。遍历字符串的每个字符，以其为中心向两边扩散，记录最大的回文子串长度。

需要注意的是对于奇数长度的字符串子串，中心可以是中间一位：aba 以b为中心向两边扩散。

而偶数长度的字符串子串，中心却应该是两位，否则不能完全扩散到子串的每一位：abba以索引1、2为中心，向两边扩散。

所以，每次循环，寻找中心时，应该有两种情况，将两种情况的中心扩散结果比较，取较大的。

代码：

```java
package com.example.demo.core.Leecode;

String result = centerSpread(str);
        System.out.println(result);
    }

/**
     * 中心扩散法
     * @param str
     * @return
     */
    public static String centerSpread(String str) {
        //特殊情况处理:null、""和1个字符
        if (str == null) {
            throw new RuntimeException("字符串不能为null");
        }
        if (str.length() <= 1) {
            return str;
        }

//记录起始索引值，和最长回文子串的长度
        int startIndex = 0, maxLen = 1;
        //validPalindrome方法内要用，这里直接定义一下，不用每次都获取了
        char[] charStr = str.toCharArray();
        //这里 - 1 是因为最后一位无法作为第二种情况的第二个扩散起点，所以到倒数第二位就截止了
        for (int i = 0; i < str.length() - 1; i++) {
            //如果子串长度是奇数的话，中心点是1个索引: a b a
            int len1 = centerValidPalindrome(charStr, i, i);
            //如果子串长度是偶数的话，中心点是2个索引: a b b a
            int len2 = centerValidPalindrome(charStr, i, i + 1);
            int currentPalindromeStrLen = len1 > len2 ? len1 : len2;
            if (currentPalindromeStrLen > maxLen) {
                //针对奇数和偶数时，startIndex和currentPalindromeStrLen的规则，可以演算一下就知道了
                startIndex = i - (currentPalindromeStrLen - 1) / 2;
                maxLen = currentPalindromeStrLen;
            }
        }
        return str.substring(startIndex, startIndex + maxLen);
    }

/**
     * 从指定中心点开始向两边扩散，找出最长回文子串并返回长度
     * @param charStr 字符串转换的字符数组
     * @param center1 中心的左边
     * @param center2 中心的右边
     * @return 回文子串的长度
     */
    private static int centerValidPalindrome(char[] charStr, int center1, int center2) {
        while (center1 >= 0 && center2 < charStr.length) {
            if (charStr[center1] != charStr[center2]) {
                break;
            }
            center1--;
            center2++;
        }
        // a b a b c b a
        // 0 1 2 3 4 5 6
        /*
        center1 = 1
        center2 = 7
        //这里-1 +1是因为跳出while循环时两个边界都是不符合的，都超了1个位置，所以要移回来
        (center2 - 1) - (center1 + 1) + 1 = center2 - 1 - center1 - 1 + 1 = center2 - center1 - 1
         */
        return center2 - center1 - 1;
    }
}
```

#### 三、动态规划：

思路：

动态规划无非就是记录已经得到过的结果，下次用到时直接使用不用再计算了，用空间换时间的算法。关键点时找到初始状态和状态转移方程。首先，我们需要一个二维数组来储存结果，定义boolean类型的二维数组dp，`dp[i][j]`代表以i为起点以j为终点的子串是否是回文，true代表回文。初始状态`dp[0][0]`肯定是true。状态转移方程：若`dp[i][j]`为true，且(i-1)和(j+1)两个位置字符相同，则`dp[i-1][j+1]`为true。

代码：

```java
package com.example.demo.core.Leecode;

String result = dynamicPro(str);
        System.out.println(result);
    }

/**
     * 动态规划
     * @param str
     * @return
     */
    private static String dynamicPro(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        int startIndex = 0;
        int endIndex = 0;
        int maxLen = 1;
        int strLen = str.length();
        boolean[][] dp = new boolean[strLen][strLen];
        char[] chars = str.toCharArray();

//必须外循环是右端点，内循环是左端点。相反的遍历方式会导致判断当前串时，有些子串没有记录，但是它可能是true，没有记录会导致false，最终导致当前串是false。
        //这种遍历的好处是遍历当前串时所有子串都已遍历得出结果
        for (int right = 1; right < strLen; right++) {
            for (int left = 0; left < right; left++) {
                //这个if是判断转移过程，注意right - left <= 2是用来处理三个字符的子串 aba ,a==a且长度是3以内
                if (chars[left] == chars[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                    if (right - left + 1 > maxLen) {
                        maxLen = right - left + 1;
                        startIndex = left;
                        endIndex = right;
                    }
                }
            }
        }
        return str.substring(startIndex, endIndex + 1);
    }
}
```

算法题--最长回文子串

文章目录

发表评论