Самая длинная палиндроми c подстрока. Что может быть временем выполнения для нижеприведенного DP + рекурсивного подхода. Это O (n ^ 2) или O (n ^ 3)

Question

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] представляет максимальную строку палиндроми c между индексами i, j. В конце мы вернем dp [0] [s.length () - 1]

Анализ кода:

Если строка (скажем, b) имеет длину 1, максимальный палиндром, который мы можем получить из него саму строку (б). Теперь давайте расширим строку до следующего + b +. Какой будет самая длинная строка палиндроми c, если знаки + заменены некоторыми алфавитами. Мы можем рассмотреть две возможности: i) оба алфавита одинаковы ii) оба они различны. Если случай i ->, мы можем сказать, что вся строка является палиндромом, поскольку мы знали, что строка между алфавитами является полностью палиндромом. В случае ii -> у нас будет две возможности: рассмотреть левую и игнорировать правую или рассмотреть правую и игнорировать левую. Тот, который мы ищем, это тот, который выдает максимальную строку палиндроми c.

Основываясь на этой идее, мы заполним весь массив dp.

Я знаю сложность пространства для алгоритма O (n ^ 2), но какова сложность времени выполнения. Это O (n ^ 2) или O (n ^ 3)?

Answer 1

Что касается сложности вашего al go, вы можете посчитать, сколько раз вы вычисляете 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)