网站类网站开发,网站建设 互诺科技,合肥计算机培训机构,网站搭建外贸转到力扣 考察知识#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)
