力扣---最长回文子串(动态规划)

2023-12-18 17:24:56

目录

?编辑

题目

思路步骤:

代码

我的其他博客


题目
?

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

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

示例 1:

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

示例 2:

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

提示:

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

思路步骤:

  1. 初始化状态: 创建一个二维数组 dp,其中 dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否是回文串。初始化所有长度为 1 的子串为回文串。

  2. 处理长度为 2 的子串: 遍历字符串,检查相邻字符是否相等,如果相等则将 dp[i][i+1] 设为 true,表示长度为 2 的子串是回文串。

  3. 处理长度为 3 或更大的子串: 使用一个嵌套循环,外层循环控制子串的长度 len,内层循环遍历字符串,检查从索引 i 到索引 j 的子串是否是回文串。如果 dp[i+1][j-1]trues.charAt(i) == s.charAt(j),则说明当前子串也是回文串。

  4. 记录最长回文子串: 在内层循环中,如果发现新的回文子串长度比之前记录的最长回文子串更长,则更新 startmaxLength

  5. 返回结果: 最终,返回最长回文子串 s.substring(start, start + maxLength)

要使用动态规划解决这个问题,首先要定义状态和状态转移方程。在这里,我们可以定义一个二维数组 dp,其中 dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否是回文串。

代码

public class LongestPalindromeSubstring {

    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int maxLength = 1;

        // All substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // Check substrings of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }

        // Check substrings of length 3 or more
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;  // Ending index of the substring

                // Check if the substring is a palindrome and the inner substring is also a palindrome
                if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    start = i;
                    maxLength = len;
                }
            }
        }

        return s.substring(start, start + maxLength);
    }

    public static void main(String[] args) {
        String s1 = "babad";
        String s2 = "cbbd";

        System.out.println(longestPalindrome(s1));  // Output: "bab" or "aba"
        System.out.println(longestPalindrome(s2));  // Output: "bb"
    }
}

?

我的其他博客

探索灵活性与可维护性的利器:策略(Strategy)模式详解-CSDN博客

深入探讨敏捷开发项目管理流程与Scrum工具:构建高效团队与卓越产品的秘诀-CSDN博客

vue的生命周期-CSDN博客

什么是tomcat?tomcat是干什么用的?-CSDN博客

Linux 压缩、解压文件的 4 种方式。tar、gzip、gunzip、zip、unzip、7z命令使用方法-CSDN博客

腾讯-轻量应用服务器centos7中宝塔安装MySQL8.0出现内存不足-CSDN博客

JVM的类的生命周期-CSDN博客

多线程------Future异步任务-CSDN博客

文章来源:https://blog.csdn.net/AliceNo/article/details/135064432
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。