超级单页网站模板,wordpress 分享到微信二维码,计算机培训班学费,新乡网站建设设计公司力扣热门100题 - 5.最长回文子串 题目链接#xff1a;5. 最长回文子串
题目描述#xff1a;
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。示例#xff1a;
输入#xff1a;s 5. 最长回文子串
题目描述
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。示例
输入s babad
输出bab
解释aba 同样是符合题意的答案。输入s cbbd
输出bb提示
1 s.length 1000
s 仅由数字和英文字母组成解题思路动态规划
创建一个二维布尔数组 dp其中 dp[i][j] 表示字符串从索引 j 到 i 的子串是否为回文串。
同时初始化 startIndex 和 maxLen分别表示最长回文子串的起始索引和长度。
使用两层嵌套循环遍历字符串。外层循环控制结束索引 i内层循环控制起始索引 j。
对于每一对索引 (i, j)检查当前字符是否相等且满足回文条件。状态转移方程为dp[i][j] chs[i] chs[j] ((i - j 1 3) || dp[i - 1][j 1])
其中(i - j 1 3) 表示当前子串长度小于等于3直接满足回文条件dp[i - 1][j 1] 表示去掉两端字符后的子串也是回文串。
如果当前子串为回文且长度大于 maxLen则更新 maxLen 和 startIndex。
最终返回最长回文子串通过 startIndex 和 maxLen 在原始字符串中截取。
时间复杂度 O(n^2)代码
public String longestPalindrome(String s) {int len s.length();// 长度小于二一定是回文串直接返回if (len 2) return s;char[] chs s.toCharArray();boolean[][] dp new boolean[len][len];int startIndex 0;int maxLen 1; for (int i 1; i len; i) {for (int j 0; j i; j) {if (chs[i] chs[j] ((i - j 1 3) || dp[i - 1][j 1])) {dp[i][j] true;if (i - j 1 maxLen) {maxLen i - j 1;startIndex j;}} else {dp[i][j] false;}}}return s.substring(startIndex, startIndex maxLen);}
