LeetCode_动态规划_中等_5.最长回文子串

我会带着你远行 2023-10-06 18:09 38阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
输入：s = “babad”  
输出：“bab”  
解释：“aba” 同样是符合题意的答案。

**示例 2：**  
输入：s = “cbbd”  
输出：“bb”

**示例 3：**  
输入：s = “a”  
输出：“a”

**示例 4：**  
输入：s = “ac”  
输出：“a”

**提示：**  
1 <= s.length <= 1000  
s 仅由数字和英文字母（大写和/或小写）组成  
“回文串”是一个正读和反读都一样的字符串，比如 “level” 或者 “noon” 等等就是回文串

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

## 2.思路 ##

（1）暴力穷举法  
先编写一个判断字符串是否为回文串的方法，然后再使用两层 for 循环，用该方法对字符串 s 的每一个子串进行判断，若该子串是回文串，则保存该子串本身以及其长度，并且与上一个结果进行比较（如果存在），取它们之间长度更大的一个即可。此外，当 s 剩余子串的长度小于当前已找到的回文子串的长度时，直接返回结果即可，这样可以提高效率。

（2）动态规划  
思路参考[本题官方题解][Link 1]。

① 对于一个长度大于 2 的子串而言，如果它是回文串，那么将它首尾的两个字母去除之后，它仍然是个回文串，例如对于字符串 “level”。

② 根据这样的思路，我们就可以用**动态规划**的方法解决本题。我们`用 dp[i][j] 表示字符串 s 的第 i 到 j 个字母组成的串（下文表示成 s[i : j]）是否为回文串`，具体如下所示：

d p \[ i \] \[ j \] = \{ t r u e , 如果子串 s \[ i : j \] 是回文串 f a l s e , 其它情况 dp\[i\]\[j\] = \\begin\{cases\} true, 如果子串 s\[i : j\] 是回文串\\\\ false, 其它情况\\end\{cases\} dp\[i\]\[j\]=\{ true,如果子串s\[i:j\]是回文串false,其它情况

这里的「其它情况」包含两种可能性：

*  s\[i : j\] 本身不是一个回文串；
 *  i > j，此时 s\[i, j\] 本身不合法。

③ 那么我们就可以写出动态规划的**状态转移方程**：

dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])

也就是说，只有 s\[i + 1 : j - 1\]是回文串，并且 s 的第 i 和 j 个字母相同时，s\[i : j\] 才会是回文串。

④ 上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

\{ d p \[ i \] \[ j \] = t r u e d p \[ i \] \[ i + 1 \] = ( s \[ i \] = = s \[ i + 1 \] ) \\begin\{cases\} dp\[i\]\[j\] = true\\\\ dp\[i\]\[i + 1\] = (s\[i\] == s\[i + 1\])\\end\{cases\} \{ dp\[i\]\[j\]=truedp\[i\]\[i\+1\]=(s\[i\]==s\[i\+1\])

⑤ 根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 dp\[i\]\[j\] = true 中 j - i + 1（即子串长度）的最大值。注意：**在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。**

（3）中心扩展法  
遍历整个字符串，**对所有的回文中心进行扩展，直到无法扩展为止**，此时的回文串长度即为此回文中心下的最长回文串长度。然后取所有的长度中的最大值，即可得到最终的答案。但是自己在写代码时出现了问题，自己只考虑到了回文串长度为奇数的情况，即以某个字符为中心然后同时向两边扩展。但其实还有一种情况，那就是**以当前字符和其下一个相邻字符为中心再向两边扩展，此时得到的回文串长度就为偶数**。所以代码一直写的有问题，最后的代码还是参考本题的官方题解。

相关题目：  
[LeetCode\_回溯\_动态规划\_中等\_131.分割回文串][LeetCode_131.]  
[LeetCode\_双指针\_简单\_234.回文链表][LeetCode_234.]  
[LeetCode\_贪心算法\_简单\_409.最长回文串][LeetCode_409.]  
[LeetCode\_动态规划\_中等\_516.最长回文子序列][LeetCode_516.]  
[LeetCode\_字符串\_中等\_647. 回文子串][LeetCode_647.]  
[LeetCode\_双指针\_简单\_1332.删除回文子序列][LeetCode_1332.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public String longestPalindrome(String s) {
        
            int maxLength = 0, length;
            String substr = "";
            for (int i = 0; i < s.length(); i++) {
        
                for (int j = i; j < s.length(); j++) {
        
                    if (isPalindrome(s.substring(i, j + 1))) {
        
                        length = s.substring(i, j + 1).length();
                        if (length > maxLength) {
        
                            maxLength = length;
                            substr = s.substring(i, j + 1);
                        }
                    }
                }
                //剩余子串的长度小于当前找到的回文子串的长度时，直接返回结果即可
                if (maxLength > s.length() - 1 - i) {
        
                    return substr;
                }
            }
            return substr;
        }
        
        //判断字符串 str 是否为回文串
        public boolean isPalindrome(String str) {
        
            int length = str.length();
            int front = 0, rear = length - 1;
            while (front <= rear) {
        
                if (str.charAt(front) != str.charAt(rear)) {
        
                    return false;
                }
                front++;
                rear--;
            }
            return true;
        }
    }

//思路2————动态规划
    class Solution {
        
        public String longestPalindrome(String s) {
        
            int length = s.length();
            //dp[i][j] 为 true 表示 s[i...j] 为回文串，否则不是
            boolean[][] dp = new boolean[length][length];
            //初始化，即长度为 1 的子串都是回文串
            for (int i = 0; i < length; i++) {
        
                dp[i][i] = true;
            }
            int start = 0;
            int maxLen = 1;
            //枚举子串长度 L
            for (int L = 2; L <= length; L++) {
        
                //枚举左边界 i，同时由 L 可以确定右边界
                for (int i = 0; i < length; i++) {
        
                    //由 L 和 i 可以确定右边界 j，即有由 L = j - i + 1 得
                    int j = L + i - 1;
                    //此时当前子串为 s[i : j]，如果右边界 j 越界，则直接退出当前循环
                    if (j >= length) {
        
                        break;
                    }
                    //状态转移
                    if (s.charAt(i) != s.charAt(j)) {
        
                        dp[i][j] = false;
                    } else {
        
                        if (i + 1 == j) {
        
                            dp[i][j] = true;
                        } else {
        
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }
                    //只要 dp[i][j] == true 成立，就表示子串 s[i...j] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && L > maxLen) {
        
                    	start = i;
                        maxLen = L;
                    }
                }
            }
            return s.substring(start, start + maxLen);
        }
    }

//思路3————中心扩展法
    class Solution {
        
        public String longestPalindrome(String s) {
        
            int length = s.length();
            int start = 0;
            int maxLen = 1;
            for (int i = 0; i < length - 1; i++) {
        
                int curLen = Math.max(expand(s, i, i), expand(s, i, i + 1));
                //更新回文串的起始位置和对应最大长度
                if (curLen > maxLen) {
        
                	start = i - (curLen - 1) / 2;
                    maxLen = curLen;
                }
                //当剩下的字符串长度不足当前最长回文子串长度一半的时候，直接跳出循环
                if ((length - i + 1) * 2 < maxLen) {
        
                    break;
                }
            }
            return s.substring(start, start + maxLen);
        }
    
        //以 s[left : right] 为中心开始扩展，返回得到的最大回文子串长度，此处的 left 可以等于 right
        public int expand(String s, int left, int right) {
        
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        
                left--;
                right++;
            }
            return right - left - 1;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
[LeetCode_131.]: https://blog.csdn.net/weixin_43004044/article/details/125341429
[LeetCode_234.]: https://blog.csdn.net/weixin_43004044/article/details/122763107
[LeetCode_409.]: https://blog.csdn.net/weixin_43004044/article/details/126935075
[LeetCode_516.]: https://blog.csdn.net/weixin_43004044/article/details/126813021
[LeetCode_647.]: https://blog.csdn.net/weixin_43004044/article/details/124979183
[LeetCode_1332.]: https://blog.csdn.net/weixin_43004044/article/details/127058795