最长回文子串（动态规划）

酒楼

发布于 2023-12-30 00:07:43

13700

代码可运行

文章被收录于专栏：酒楼酒楼

运行总次数：0

代码可运行

最长回文子串

一，题目

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

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

二，我的解法（暴力解法）

class Solution {
    public String longestPalindrome(String inputStr) {
        String result = inputStr.substring(0, 1);
        String aimStr = "";
        int tail = 0;
        int head = 0;
        int length = inputStr.length();

        if (inputStr != null && !inputStr.isEmpty()) {
            // String[] nums = buildNums(inputStr);
            for (int i = 0; i < length; i++) {
                tail = i + 1;
                head = i;
                if (head > 0 && tail < length && inputStr.charAt(head - 1) == (inputStr.charAt(tail))) {
                    head--;
                    while (head >= 0 && tail < length && inputStr.charAt(head) == (inputStr.charAt(tail))) {
                        head--;
                        tail++;
                    }
                }
                System.out.println("head: " + head + 1);
                System.out.println("tail: " + tail);
                aimStr = inputStr.substring(head + 1, tail);
                if (aimStr.length() > result.length()) {
                    result = aimStr;
                }
                tail = i + 1;
                head = i;
                while (head >= 0 && tail < length && inputStr.charAt(head) == (inputStr.charAt(tail))) {
                    head--;
                    tail++;
                }
                System.out.println("head: " + head + 1);
                System.out.println("tail: " + tail);
                aimStr = inputStr.substring(head + 1, tail);
                if (aimStr.length() > result.length()) {
                    result = aimStr;
                }

            }
        }

        return result;
    }
}

三，官方解法（动态规划）

public class Solution{
    public String longestPalindrome(String s){
        int len = s.length();
        if(len < 2){
            return s;
        }
        
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为1的字串都是回文串
        for(int i=0;i<len;i++){
            dp[i][i] = true;
        }
        
        char[] charArray = s.toCharArray();
        //递推开始
        //先枚举子串长度
        for(int L = 2;L<=len;L++){
            //枚举左边界，左边界的上限设置可以宽松一些
            for(int i = 0 ;i<len;i++){
                //由 L 和i可以确定有边界，即 j-i+1=L得
                int j = L + i -1;
                //如果右边界越界，就可以退出当前循环
                if(j >= len){
                    break;
                }
                
                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];
                    }
                }
                
                //只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if(dp[i][j] && j-i+1>maxLen){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}