• 關(guān)鍵字：動(dòng)態(tài)規(guī)劃、回文字符串
• 難度：Medium
• 題目大意：輸出一個(gè)字符串的最長回文子串

題目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解題思路：

• 思路一：
  以每一個(gè)字符為中心，往兩邊擴(kuò)散來找，需要考慮字符串長度為奇 數(shù)和偶數(shù)的情形；
• 思路二：動(dòng)態(tài)規(guī)劃，以p(i,j)表示從字符串下標(biāo)i到下標(biāo)j字符是否為回文串，則可分情況討論：
  • i==j時(shí)：
    p(i, j) = true
  • j-i=1時(shí)：
    p(i, j)=s.charAt(i)==s.charAt(j) j-i=1;
  • j-i>1時(shí)：
    p(i, j)=s.charAt(i)==s.charAt(j)&&( j-i<2||p(i+1,j-1));

填充dp數(shù)組時(shí)，注意逆序填充，可結(jié)合下圖例子理解：

逆序填充DP.jpeg

解法1：

class Solution {
        public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return s;
        int len = s.length();
        int maxLen = 1;
        int start = 0;
        for(int i=0;i<len;i++) {
            //需要考慮字符串長度為奇數(shù)偶數(shù)的問題
            int cur = Math.max(process(s,i,i,maxLen),process(s,i,i+1,maxLen)); 
            if(cur>maxLen) {
                maxLen = cur;
                start = i-(maxLen-1)/2;
            }
        }

        return s.substring(start,start+maxLen);
    }
    private int process(String s, int l, int r,int maxLen){
        while(l>=0&&r<s.length()) {
            if(s.charAt(l)==s.charAt(r)) {
                if(maxLen<r-l+1) {
                    maxLen = r-l+1;
                }
                l--;
                r++;
            }
            else{
                   break; 
                }
        }
        return maxLen;
    }
}

解法2：

class Solution {
    public static String longestPalindrome(String s) {
        if(s==null||s.length()==0) return s;
        int len = s.length();
        boolean [][] dp = new boolean[len+1][len+1];
        int maxLen = 1;
        int start = 0;
        //初始化i==j時(shí)dp數(shù)組的值為true
        for(int i=1;i<len+1;i++) {
            for(int j=1;j<len+1;j++) {
                if(j==i) dp[i][j] = true;
            }
        }
        //根據(jù)上述遞推式，可知dp二維數(shù)組需要逆序填充
        for(int i=len;i>0;i--) {
            for(int j=len;j>i;j--) {
                if(s.charAt(i-1)==s.charAt(j-1)&&(dp[i+1][j-1]||j-i<2)) {
                    dp[i][j] = true;
                    if(maxLen<j-i+1) {
                        maxLen = j-i+1;
                        start = i-1;
                    }
                }

            }
        }
        return s.substring(start,start+maxLen);
    }

}