LeetCode - 5 最长回文子串

动态规划

class Solution {
    
    public String longestPalindrome(String s) {
    
       int n = s.length();
       boolean[][] dp = new boolean[n][n];
       int len = 0;
       String ans = "";
       for(int i = n-1; i >=0;i--){
    
           for(int j = i; j < n;j++){
    
               if(j == i){
    
                  dp[i][j] = true;
               }
                else if(j - i == 1){
    
                   dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                else{
    
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }

                if(dp[i][j] == true){
    
                    if(j-i+1 > len){
    
                        len = j-i+1;
                        ans = s.substring(i,j+1);
                    }
                }
           }
       }
       return ans;
    }
}

中心扩散

class Solution {
    
    int len = 0;
    String ans = "";
    public String longestPalindrome(String s) {
    
       int n = s.length();
       for(int i = 0; i<n;i++){
    
           centerSpread(s,i,i);
           if(i < n-1)
             centerSpread(s,i,i+1);
       }
       return ans;
    }
    public void centerSpread(String s,int left,int right){
    
        int n = s.length();
        int i = left;
        int j = right;
        while(i>=0 && j<n && s.charAt(i) == s.charAt(j))
        {
    
            i--;
            j++;
        }
        if(j-i-1 > len){
    
            len = j-i-1;
            ans = s.substring(i+1,j);
        }
    }
}