[Java·算法·中等]LeetCode5. 最长回文子串

小鱼儿 2023-09-24 20:49 13阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1
 *  分析思路2
 *  题解2

## 题目 ##

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

## 示例 ##

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

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

## 分析思路1 ##

中心扩展算法：  
遍历所有字符串，对于每个字符都以它为中心向两边扩展，直到不是回文串为止。  
注意，因为回文串的长度可能是奇数或偶数，所以需要分别考虑这两种情况：调两次`expandAroundCenter` 方法，第三个参数是`i` 和 `i+1`。

## 题解1 ##

class Solution {
        
        public String longestPalindrome(String s) {
        
            if(s==null || s.length()<1){
        return "";}
            // 初始化最大回文子串的起点和终点
            int start=0,end=0;
            for (int i=0; i<s.length(); i++){
        
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i+1);
                int len = Math.max(len1, len2);
                if(len > end - start){
        
                    start = i - (len-1)/2;
                    end = i + len/2;
                }
            }
            return s.substring(start, end+1);
        }
        
        /**
         * @param s             输入的字符串
         * @param left          起始的左边界
         * @param right         起始的右边界
         * @return              回文串的长度
         */
        public int expandAroundCenter(String s, int left, int right){
        
            // 左右边界在0和字符长度之间，且左右边界上的字符相等，就可以将边界向左右同时移动一位
            while (left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
        
                left--;
                right++;
            }
            // left指针指向的是回文子串左侧的前一个位置，而right指针指向的是回文子串右侧的后一个位置，这两个位置都不属于回文子串本身，因此在计算长度时需要减去它们的个数2。
            // 回文串的长度是right-left+1-2 = right - left - 1
            return right - left - 1;
        }
    }

执行结果  
![在这里插入图片描述][fa4b2d44ab0e486d87a7a64a1a5e708b.png]

## 分析思路2 ##

动态规划算法：  
用一个二维的布尔型数组 `dp[i][j]` 表示从第 `i` 个字符到第 `j` 个字符是否为回文串。如果是回文串，则 `dp[i][j]` 的值为 `true`，否则为 `false`。

我们可以根据回文串的定义，得到以下状态转移方程：

当 `i = j` 时，`dp[i][j] = true`；  
当 `s[i] = s[j]` 且 `dp[i+1][j-1] = true` 时，`dp[i][j] = true`；  
否则，`dp[i][j] = false`。

根据状态转移方程，我们可以使用两层循环来填充整个数组，得到所有的 `dp[i][j]` 值。然后，我们可以根据 `dp` 数组中的信息，找到最长的回文子串。

## 题解2 ##

class Solution {
        
        public static String longestPalindrome(String s) {
        
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String res = "";
        for (int i = n - 1; i >= 0; i--) {
        
            for (int j = i; j < n; j++) {
        
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > res.length()) {
        
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
    
    }

执行结果  
![在这里插入图片描述][171205b99bbe4f12b26284336ad6a863.png]

[fa4b2d44ab0e486d87a7a64a1a5e708b.png]: https://img-blog.csdnimg.cn/fa4b2d44ab0e486d87a7a64a1a5e708b.png
[171205b99bbe4f12b26284336ad6a863.png]: https://img-blog.csdnimg.cn/171205b99bbe4f12b26284336ad6a863.png