class Solution {
public String longestPalindrome(String s) {
if(s.length() == 0){
return "";
}
String[][] dp = new String[s.length()][s.length()];
int n = s.length();
for(int i=0; i<n; i++){
dp[i][i] = s.substring(i,i+1);
}
int l = n/2;
int r = n/2;
while(!(l==0 && r==n-1)){
if(l>0){
l--;
}
if(r<n-1){
r++;
}
longest(l, r, s, dp);
}
return dp[0][n-1];
}
public String longest(int l, int r, String s, String[][] dp) {
if(dp[l][r] != null){
return dp[l][r];
} else if(s.charAt(l) == s.charAt(r) && (l == r-1 || longest(l+1, r-1, s, dp).length() == ((r-1) - (l+1))+1)){
dp[l][r] = s.substring(l,r+1);
return dp[l][r];
} else {
String l1 = longest(l, r-1, s, dp);
String l2 = longest(l+1, r, s, dp);
dp[l][r] = l1.length() > l2.length() ? l1 : l2;
return dp[l][r];
}
}
}
dp [i] [j]表示索引i,j之间的最大回文串。我们最终将返回dp [0] [s.length()-1]
代码分析:
如果字符串(例如b)的长度为1,则我们可以从中得到的最大回文数将是字符串本身(b)。现在,将字符串扩展到+ b +之后。如果用某些字母替换+号,则最长回文字符串是什么。我们可以考虑两种可能性:i)两个字母相同ii)他们都是不同的。如果是案例->,我们可以说整个字符串都是回文,因为我们知道字母之间的字符串完全是一个回文。如果情况ii->,我们将有两种可能性考虑左偏而忽略右偏,或考虑右偏而忽略左偏。我们正在寻找的是一种能够产生最大回文串的字符串。
基于这个想法,我们将填充整个dp数组。
我知道算法的空间复杂度是O(n ^ 2),但是运行时复杂度是多少。是O(n ^ 2)还是O(n ^ 3)?
关于算法的复杂性,您可能希望计算dp[l][r]
的计算次数(因此避免已经缓存了它的情况)
'a'.repeat(10^4)
,请检查您的计数。'a'.repeat(2*10^4)
的字符串执行此操作,并检查您的计数是4x还是2 ^ 3x。那是说我们可以不递归地做(而且看起来更容易)
如果长度为n的字符串是回文,则长度为n-2的字符串也将左右截断1个字符。
回文长度为偶数或奇数,所以>
让我们关注奇数回文。
假设我们的字符串长度相等。
总计:n + n-2 + ... + 0 = sum_k=0^{n/2} (n - 2k) = n*n/2 - (n/2*(n/2+1)) ~ O(n^2)
对于相等长度的回文,我们可以将其加倍,因此复杂度保持为O(n ^ 2)
function pal (n) {
console.time('go')
const s = 'a'.repeat(n)
let candidates = s.split('').map((c, i) => ({ l: i, r: i }))
s.split('').forEach((c, i) => c === s[i + 1] && candidates.push({ l: i, r: i + 1 }))
while(candidates.length) {
const next = []
candidates.forEach(({ l, r }) => {
if (l - 1 >= 0 && r + 1 < s.length && s[l - 1] === s[r + 1]) {
next.push({ l: l - 1, r: r + 1 })
}
})
if (next.length === 0) {
// print the the biggest ones, start from the bottom...
const best = candidates[candidates.length - 1]
const bestLength = best.r - best.l
candidates.filter(c => c.r - c.l === bestLength).forEach(c => console.log(c))
}
candidates = next
}
console.timeEnd('go')
}
const base = 0.2*10**4
pal(base) // (got 1.010s with base = 0.5**10^4 but this freezes UI, so... adjust yourself to have a big enough number)
pal(base*2) // expect 4 time slower (got 4.163s)
pal(base*4) // expect 16 time slower (got 16.819s)