张家港网站设计,个人做搜索网站违法吗,wordpress通过图片id获取路径,免费推广工具力扣热门100题 - 5.最长回文子串 题目描述#xff1a;示例#xff1a;提示#xff1a;解题思路#xff1a;#xff08;动态规划#xff09;代码#xff1a; 题目链接#xff1a;5. 最长回文子串
题目描述#xff1a;
给你一个字符串 s#xff0c;找到 s 中最长的回… 力扣热门100题 - 5.最长回文子串 题目描述示例提示解题思路动态规划代码 题目链接5. 最长回文子串
题目描述
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。示例
输入s babad
输出bab
解释aba 同样是符合题意的答案。输入s cbbd
输出bb提示
1 s.length 1000
s 仅由数字和英文字母组成解题思路动态规划
创建一个二维布尔数组 dp 用于记录字符串中的回文子串。初始化变量 startIndex 和 maxLen 为 0用于记录最长回文子串的起始索引和长度。遍历字符串 s 中的每个字符利用两层循环来确定所有可能的子串并检查它们是否是回文串。在内部循环中判断两个字符是否相等如果相等则有可能构成回文串。如果是的话检查子串长度是否小于等于 3此时一定是回文串或者查看子串去除两端字符后是否是回文串即 dp[i - 1][j 1] 是否为 true。如果当前子串是回文串且长度大于 maxLen则更新 maxLen 和 startIndex。最终返回从 startIndex 开始、长度为 maxLen 的子串。
时间复杂度 O(n^2)
这种方法的时间复杂度是 O(n^2)其中 n 是字符串的长度因为需要遍历整个字符串并在每个位置上检查回文串的可能性。
代码
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);}
