最长回文子串。以下DP +递归方法的运行时间是多少?是O(n ^ 2)还是O(n ^ 3)

问题描述 投票:0回答:1
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)?

algorithm performance
1个回答
0
投票

关于算法的复杂性,您可能希望计算dp[l][r]的计算次数(因此避免已经缓存了它的情况)

  • 对于非常大的字符串,例如'a'.repeat(10^4),请检查您的计数。
  • 然后对两倍大'a'.repeat(2*10^4)的字符串执行此操作,并检查您的计数是4x还是2 ^ 3x。

那是说我们可以不递归地做(而且看起来更容易)

如果长度为n的字符串是回文,则长度为n-2的字符串也将左右截断1个字符。

算法

回文长度为偶数或奇数,所以>

  • 获取所有1个字符串和所有2个字符串(在后面的情况下使用相同的字符)
  • 要构建给定字符串的后继,请检查左右是否相同
  • 只要有继任者,就继续
  • 复杂度

让我们关注奇数回文。

假设我们的字符串长度相等。

  • 我们有n个长度为1的候选。
  • 我们可以构建n-2个下一个(长度为3)
  • 直到只有两个长度为n-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)
© www.soinside.com 2019 - 2024. All rights reserved.