东莞企业网站公司,芜湖做网站多少钱,天津建设厅网站首页,百度网站适配代码目录
编辑 题目
思路步骤#xff1a;
代码
我的其他博客 题目 给你一个字符串 s#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。 示例 1#xff1a; 输入#xff1a;s babad
输出
代码
我的其他博客 题目 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1 输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2 输入s cbbd
输出bb提示 1 s.length 1000s 仅由数字和英文字母组成 思路步骤 初始化状态 创建一个二维数组 dp其中 dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否是回文串。初始化所有长度为 1 的子串为回文串。 处理长度为 2 的子串 遍历字符串检查相邻字符是否相等如果相等则将 dp[i][i1] 设为 true表示长度为 2 的子串是回文串。 处理长度为 3 或更大的子串 使用一个嵌套循环外层循环控制子串的长度 len内层循环遍历字符串检查从索引 i 到索引 j 的子串是否是回文串。如果 dp[i1][j-1] 为 true 且 s.charAt(i) s.charAt(j)则说明当前子串也是回文串。 记录最长回文子串 在内层循环中如果发现新的回文子串长度比之前记录的最长回文子串更长则更新 start 和 maxLength。 返回结果 最终返回最长回文子串 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 palindromesfor (int i 0; i n; i) {dp[i][i] true;}// Check substrings of length 2for (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 morefor (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 palindromeif (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 abaSystem.out.println(longestPalindrome(s2)); // Output: bb}
}我的其他博客
探索灵活性与可维护性的利器策略Strategy模式详解-CSDN博客
深入探讨敏捷开发项目管理流程与Scrum工具构建高效团队与卓越产品的秘诀-CSDN博客
vue的生命周期-CSDN博客
什么是tomcattomcat是干什么用的-CSDN博客
Linux 压缩、解压文件的 4 种方式。tar、gzip、gunzip、zip、unzip、7z命令使用方法-CSDN博客
腾讯-轻量应用服务器centos7中宝塔安装MySQL8.0出现内存不足-CSDN博客
JVM的类的生命周期-CSDN博客
多线程------Future异步任务-CSDN博客
