【刷题】最长回文子串-动态规划

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例一

输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。

示例二

输入：s = “cbbd” 输出：“bb”

思路：

创建动态规划数组dp，初始化其中dp[i][i]=true 字符串长度为1一定是回文串,长度为2时只有两个字符相同才是回文串 如果下标从i到j的子串是回文子串，那么i和j下标对应的字符一定相同(s[i]==s[j])，并且下标i+1到j-1的子串也一定是回文子串。 if(s[i]!=s[j]),那么子串s(i:j)不是回文子串，dp[i][j]=false; if(s[i]==s[j]).dp[i][j]=dp[i+1][j-1],其中要保证i+1<=j-1;

public String longestPalindrome(String s) {
          
   
        int length=s.length();
        if(length==1)return s;
        int maxlen=1;
        int begin=0;
        String res;
        boolean[][] dp = new boolean[length][length];
        for(int i=0;i<length;i++){
          
   
            dp[i][i]=true;
        }
        char[] getString = s.toCharArray();
        for (int L = 1; L <length ; L++) {
          
   
            for(int i=0;i<length;i++){
          
   
                int j=L+i;
                if(j>=length)break;
                if(getString[i]!=getString[j])
                    dp[i][j]=false;
                else{
          
   
                    if(i+1<=j-1){
          
   
                        dp[i][j]=dp[i+1][j-1];
                    }else{
          
   
                        dp[i][j]=true;
                    }
                }
                if(dp[i][j]&&j-i+1>maxlen){
          
   
                    maxlen=j-i+1;
                    begin=i;
                }
            }

        }
        return s.substring(begin,begin+maxlen);
    }