leetcode 4 - 最长回文子串

2021-08-19 本文已影响0人那钱有着落吗

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

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

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

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

题解

首先看到这个题，我们可以理解一下，既然是回文的话，那么按照我们的理解就像洋葱一样，一层一层的剥下去，第一次两边的字符是一样，去掉之后最外层的两个字符依然应该是一样的这么依次去对比，如果都符合要求，那么这个字符串就是回文串了，这个其实就是动态规划的原理了，就是可以将大的问题分解为一个个小的问题。

public class Solution3 {
    // 动态规划法:面试选这个解法
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] cs = s.toCharArray();
        // dp[i][j]:表示s[i][j]是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：单独一个字符肯定是回文子串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // 经验：dp区域是正方形的话，通常左下角区域无效不需要再填，因为走过的区域不用再走
        for (int j = 1; j < len; j++) { // 上三角区域，按列从上到下填
            for (int i = 0; i < j; i++) {
                // 首尾不相等时，必不是回文串
                if (cs[i] != cs[j]) {
                    dp[i][j] = false;
                } else {
                    // 首尾相等时，有2种情况
                    // 情况1：s[i...j]长度不超过3，不用检查必为回文串
                    // 情况2：s[i...j]长度大于3，由s[i+1...j-1]来判断
                    dp[i][j] = j - i + 1 <= 3 || dp[i + 1][j - 1];
                }
                // 更新max和begin
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

}

备注一下：

if (cs[i] != cs[j]) {
                    dp[i][j] = false;
                } else {
                    // 首尾相等时，有2种情况
                    // 情况1：s[i...j]长度不超过3，不用检查必为回文串
                    // 情况2：s[i...j]长度大于3，由s[i+1...j-1]来判断
                    dp[i][j] = j - i + 1 <= 3 || dp[i + 1][j - 1];
                }

这块程序可能有人看不懂，我们可以使用一个例子来自己推导一下即可：“ABCCBAD”；

首先外层的循环j是从1开始的，因为0这个没必要验证，每一个单独的字符串本身就作为一个回文串，所以最小的回文串是1；
外层循环从j开始，然后i从0到小于j的位置，也就是说如果拿例子来说的话，第一个ture就出现在，j的位置在第二个C，然后i的位置在第一个C的时候
第二次出现true是当j位置在第二个B，然后i的位置在第一个B的时候，我们可以看得出来BCCB是个回文串，但是程序里并不知道，如果两个B中间是AC呢？所以在这行代码就比较核心和智慧了：

dp[i][j] = j - i + 1 <= 3 || dp[i + 1][j - 1];

首先当i和j之间总共三个字符，因为之前已经判断i和j位置的字母一样，那么这个肯定就是个回文了，然后如果是两个字符串，那也因为之前判断了值一直所以是个回文串；而dp[i + 1][j - 1]就类似于开头说的剥洋葱一样，在CC的时候我们就已经给dp[i][j]给赋值为true了，所以如果我们能判断出BB之间的CC这两个字符是true的状态，那么就证明BCCB是个回文串了。

然后当遇到 ABCCBA的时候就同理了，我们知道BCCB是个回文串，那么A又等于A，所以ABCCBA就是个回文串了，别问我怎么知道BCCB是个回文串，因为在之前的我们已经证明过了，更别问我为什么BCCB内的CC是个回文串，第一次就证明了的。

在梳理下：

1.证明CC是个回文串
2.因为CC是个回文串，且B=B,证明BCCB是个回文串
3.因为BCCB是个回文串，所以证明ABCCBA是个回文串

leetcode 4 - 最长回文子串

题解

猜你喜欢

热点阅读