5. 最长回文子串

傷城~ 2022-12-29 09:39 204阅读 0赞

# [5. 最长回文子串][5.] #

## 1、参考资料 ##

[LeetCode 官方题解][LeetCode]

## 2、题目要求 ##

> **题目描述**

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

> **示例 1：**

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

> **示例 2：**

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

## 3、代码思路 ##

> 方法一：中心扩散法

算法思想

1.  枚举所有可能的回文子串的中心位置；
2.  中心位置可能是一个字符，也有可能是两个相邻的字符；
3.  记录最长回子文串的相关变量。

![image-20201221202306925][]

--------------------

算法步骤

1.  我们遍历字符串 `str` 中的每一个字符，以该字符为中心，向两边扩散求最长回文字符串
2.  对于 `"xabay"` 这种字符串，存在中心对称点，左指针 `left` 和右指针 `right` 同时指向字符 `'b'` ，然后向两侧扩展
3.  对于 `"xabbay"` 这种字符串，不存在中心对称点，左指针 `left` 指向左侧的字符 `b` ，右指针 `right` 指向右侧的字符 `b`，然后向两侧扩展
4.  我们在遍历字符串 `str` 中的每一个字符，存在中心对称点和不存在中心对称点的情况都要考虑到，`expandFromCenter()` 方法以 `left`，`right` 为中心起点，向两侧扩展，寻找回文字符串
5.  考虑到程序性能，我们在 `expandFromCenter()` 方法中，选择返回回文字符串的长度，并不是返回左右边界的索引 `int[] {left, right}`，就是将链表长度再转换左右边界索引的时候，逻辑有点绕，举一些例子就明白了

--------------------

算法复杂度：

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

空间复杂度：O(1)

> 方法二：动态规划法

动态规划

1.  状态定义：`dp[i][j]` 表示子串 `s[i...j]` 是否为回文子串
2.  状态转移：`dp[i][j] = (s[i] == s[j]) and dp[i + 1][i - 1]` ，即 `s[i...j]` 为回文子串的条件为：`s[i] == s[j]` 并且 `s[i+1...j-1]` 也为回文子串
3.  边界条件：`j - 1 - (i + 1) + 1 < 2`，即当子串 `s[i+1...j-1]` 长度小于 `2` 时，子串 `s[i+1...j-1]` 肯定是回文子串，整理可得 `j - i < 3`
4.  初始化条件：`dp[i][i] = true`，即长度为 `1` 的子串均为回文子串
5.  输出：在得到一个状态的值为 `true` 的时候，记录起始位置和长度，填表完成以后再截取

--------------------

综上可得状态转移方程：`dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i + 1][i - 1])`

由于`dp[i][j]`参考它左下方的值：

1.  先升序填列
2.  再升序填行

![image-20201221204430312][]

--------------------

举个栗子

1.  初始化对角线
    
    ![image-20201221204645875][]
2.  升序填第 1 列
    
    ![image-20201221204650196][]
3.  升序填第 2 列
    
    ![image-20201221204654493][]
4.  升序填第 3 列
    
    ![image-20201221204658300][]
5.  升序填第 4 列
    
    ![image-20201221204705579][]

--------------------

算法复杂度分析

时间复杂度：O(n2)

空间复杂度：O(n2)

## 4、代码实现 ##

> 1、中心扩散法：时间复杂度 O(n2)，空间复杂度 O(1)

/**
     * @ClassName LongestPalindromeDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/3 14:22
     * @Version 1.0
     */
    public class LongestPalindromeDemo {
        
    
        public static void main(String[] args) {
        
            Solution solution = new Solution();
            String longestPalindrome = solution.longestPalindrome("babad");
            System.out.println(longestPalindrome);
        }
    
    }
    
    class Solution {
        
        /**
         * 求 str 的最长回文字符串
         *
         * @param str 输入的字符串
         * @return str 的最长回文字符串
         */
        public String longestPalindrome(String str) {
        
    
            // Gurad safe
            if (str == null || str.length() < 1) {
        
                return "";
            }
    
            int start = 0;
            int end = 0;
            // 遍历字符串中每一个字符
            for (int i = 0; i < str.length(); i++) {
        
                // 以当前字符为中心对称点，以 i 为中心向两边扩散
                int len1 = expandFromCenter(str, i, i);
                // 无中心对称点，，以 i 为左指针，i+1 为右指针，向两边扩散
                int len2 = expandFromCenter(str, i, i + 1);
                // 求得最大的回文串长度
                int len = Math.max(len1, len2);
                // 如果当前回文串长度大于之前的回文串长度
                if (len > end - start) {
        
                    // 对于 "xabay" 这种字符串，len = 3 为奇数
                    // 对于 "xabbay" 这种字符串，len = 4 为偶数
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            // 返回最长回文字符串
            return str.substring(start, end + 1);
    
        }
    
        /**
         * 中心扩展法求 str 的最长回文字符串
         * 如果匹配像 "aba" 这样有中心对称点的字符串，left == right
         * 但如果匹配像 "abba" 这样没有中心对称点的字符串，right = left + 1
         *
         * @param str   源字符串
         * @param left  left 起点
         * @param right right 起点
         * @return 回文字符串的长度
         */
        public int expandFromCenter(String str, int left, int right) {
        
    
            while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
        
                left--;
                right++;
            }
    
            // 回文字符串的长度
            // 对于 "xabay" 这种字符串，执行完成后 left 指向 x，right 指向 y，right - left - 1 = 3，为回文字符串的长度
            // 对于 "xabbay" 这种字符串，执行完成后 left 指向 x，right 指向 y，right - left - 1 = 4，为回文字符串的长度
            return right - left - 1;
        }
    }

> 2、动态规划

class Solution {
        
        public String longestPalindrome(String str) {
        
            int len = str.length();
    
            // 字符串长度为 1，最长回文子串就是它自己
            if (len < 2) {
        
                return str;
            }
    
            boolean[][] dp = new boolean[len][len];
            int maxLen = 1;
            int begin = 0;
    
            // 初始化对角线，含义为：长度为 1 的子串均为回文子串
            for (int i = 0; i < len; i++) {
        
                dp[i][i] = true;
            }
    
            char[] charArray = str.toCharArray();
    
            // 从第一列到最后一列
            for (int j = 1; j < len; j++) {
        
                // 从第 0 行到对角线上面一行
                for (int i = 0; i < j; i++) {
        
                    // 无法构成回文子串
                    if (charArray[i] != charArray[j]) {
        
                        dp[i][j] = false;
                    } else {
        
                        // 边界条件
                        if (j - i < 3) {
        
                            dp[i][j] = true;
                        } else {
        
                            dp[i][j] = (dp[i + 1][j - 1]);
                        }
                    }
                    // 实时记录边界
                    if (dp[i][j] == true && j - i + 1 > maxLen) {
        
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return str.substring(begin, begin + maxLen);
        }
    }

[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[LeetCode]: https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
[image-20201221202306925]: /images/20221120/7eece91e51f34af0a4138cb8c762de72.png
[image-20201221204430312]: /images/20221120/d585fc9d308344188c8d90d87676474f.png
[image-20201221204645875]: /images/20221120/13592dd6922e48118de7fcaf6446c443.png
[image-20201221204650196]: /images/20221120/80f0fc5c0d844e91b13600db9ea57efe.png
[image-20201221204654493]: /images/20221120/79038991017b44afbd8f04791370c7ad.png
[image-20201221204658300]: /images/20221120/82475d250e304c03b3cae78ef036fec8.png
[image-20201221204705579]: /images/20221120/23a7047592be4804a50bcdbe9cc34e9c.png