LeetCode-5. 最长回文子串

﹏ヽ暗。殇╰゛Y 2024-03-24 13:18 68阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划

题目来源  
[5. 最长回文子串][5.]

### 题目思路 ###

本题和[LeetCode-647. 回文子串][LeetCode-647.]基本一样，只是增加了几行代码

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

布尔类型的dp\[i\]\[j\]：表示区间范围\[i,j\] （注意是左闭右闭）的子串是否是回文子串，如果是dp\[i\]\[j\]为true，否则为false。

*  2.确定递推公式

在确定递推公式时，就要分析如下几种情况。  
整体上是两种，就是s\[i\]与s\[j\]相等，s\[i\]与s\[j\]不相等这两种。  
**当s\[i\]与s\[j\]不相等，那没啥好说的了，dp\[i\]\[j\]一定是false。**  
**当s\[i\]与s\[j\]相等时，这就复杂一些了，有如下三种情况**

*  情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
 *  情况二：下标i 与 j相差为1，例如aa，也是文子串
 *  情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s\[i\]与s\[j\]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp\[i + 1\]\[j - 1\]是否为true。

if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            dp[i][j] = true;
                        }
                    }

注意这里我没有列出当s\[i\]与s\[j\]不相等的时候，因为在下面dp\[i\]\[j\]初始化的时候，就初始为false。

在得到\[i,j\]区间是否是回文子串的时候，直接保存最长回文子串的左边界和右边界，代码如下：

if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            dp[i][j] = true;
                        }
                    }
                    if(dp[i][j] && j-i+1>maxLength){
        
                        maxLength = j-i+1;
                        left = i;
                        right = j;
                    }

*  3.dp数组如何初始化

dp\[i\]\[j\]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。  
所以dp\[i\]\[j\]初始化为false。

*  4.确定遍历顺序

首先从递推公式中可以看出，情况三是根据dp\[i + 1\]\[j - 1\]是否为true，在对dp\[i\]\[j\]进行赋值true的。  
dp\[i + 1\]\[j - 1\] 在 dp\[i\]\[j\]的左下角，如图：  
所以一定要从下到上，从左到右遍历，这样保证dp\[i + 1\]\[j - 1\]都是经过计算的。  
![在这里插入图片描述][6cff245de7824328a33cb019e61f1cc2.png]

for(int i = s.length()-1;i>=0;i--){
        
                for(int j=i;j<s.length();j++){
        
                    if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            dp[i][j] = true;
                        }
                    }
                    if(dp[i][j] && j-i+1>maxLength){
        
                        maxLength = j-i+1;
                        left = i;
                        right = j;
                    }
                }
            }

*  5.举例推导dp数组

举例，输入：“aaa”，dp\[i\]\[j\]状态如下：  
![在这里插入图片描述][d98b1868887c4a6f9cbdcdf2c54b1858.png]  
代码实现

class Solution {
        
        public String longestPalindrome(String s) {
        
            boolean[][] dp = new boolean[s.length()][s.length()];
            int maxLength = 0;
            int left=0;
            int right=0;
            for(int i = s.length()-1;i>=0;i--){
        
                for(int j=i;j<s.length();j++){
        
                    if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            dp[i][j] = true;
                        }
                    }
                    if(dp[i][j] && j-i+1>maxLength){
        
                        maxLength = j-i+1;
                        left = i;
                        right = j;
                    }
                }
            }
            //左闭右开
            return s.substring(left,right+1);
        }
    }

![在这里插入图片描述][b39f649b2eb6454bad5b4380cf0b6861.png]

[5.]: https://leetcode.cn/problems/longest-palindromic-substring/
[LeetCode-647.]: https://donglin.blog.csdn.net/article/details/129897413
[6cff245de7824328a33cb019e61f1cc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2b8568d666114101ad760876e70781a8.png
[d98b1868887c4a6f9cbdcdf2c54b1858.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7c4d3833eff34aaa94087e6fbcfc0810.png
[b39f649b2eb6454bad5b4380cf0b6861.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d5112a177f414b66bb96f1f574cc5708.png