Блог

Привет, я пытаюсь решить проблему с литкодом номер 5 С самой длинной палиндромной подстрокой. Я использую стратегию DP, согласно которой я увеличиваю значение в таблице DP на 2, если это нечетный палиндром, и увеличиваю его на 1, если он четный; и я отслеживаю наибольшее значение в таблице. Я думаю, что моя стратегия-это просто O(n^2), но время выполнения чрезвычайно велико, что занимает 280 мс. Я попытался улучшить метод subString (), реализовав StringBuilder и добавив его сам, но это не сильно помогло. Я действительно не знаю, почему запуск моего кода занимает так много времени. Пожалуйста, помогите.

  class Solution {
    public String longestPalindrome(String s) {
        int size = s.length();
        int dp[][] = new int[size][size];
 
        int len = 1;
        int maxI=0;
        int maxJ=0;
        
        StringBuilder sb=new StringBuilder("");
        for (int j = 0; j < size; j  ) {
            for (int i = 0; i <= j; i  ) {
                if (i == j) {
                    dp[i][j] = 1;
                } else if(i<j){     
                    if(s.charAt(i) == s.charAt(j)){
                        if((dp[i   1][j - 1] > 0)){
                            dp[i][j] = dp[i   1][j - 1]   2;
                        }if((dp[i][j-1] == 1)){
                             dp[i][j] = 2;
                        }
                    }else {
                        dp[i][j] = 0;
                    }
                }
                if ( len<dp[i][j]||(len==dp[i][j] amp;amp; j>maxJ) ){
                    len = dp[i][j];
                    maxI= i;
                    maxJ=j;
                }

            }

        }
        return s.substring(maxI, maxJ 1);
    }
}