常州专业网站建设推广,多种网站模板,做cpa网站,该网站受海外服务器保护转到力扣 考察知识#xff1a;字符串、动态规划
这个题目力扣给的难度是中等#xff0c;感觉是中等难度题目中比较难的一个了#xff0c;写代码之前理清楚思路再去写#xff0c;
方法一、动态规划
时间复杂度#xff1a;O(n2) 空间复杂度#xff1a;O(n2)
public cla…转到力扣 考察知识字符串、动态规划
这个题目力扣给的难度是中等感觉是中等难度题目中比较难的一个了写代码之前理清楚思路再去写
方法一、动态规划
时间复杂度O(n2) 空间复杂度O(n2)
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);}
}
方法二、 中心拓展算法
时间复杂度O(n2) 空间复杂度O(1)
方法三、 Manacher 算法
时间复杂度O(n) 空间复杂度O(n)
