一、題目

Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Example
Given the string = "abcdzdcab", return "cdzdc".
Challenge
O(n2) time is acceptable. Can you do it in O(n) time.
求一個字符串中的最長回文子串。

二、解題思路

區(qū)間類動態(tài)規(guī)劃

Time O(n^2), Space O(n^2)
用dp[i][j]來存DP的狀態(tài)，需要較多的額外空間: Space O(n^2)
DP的4個要素
狀態(tài)：
dp[i][j]: s.charAt(i)到s.charAt(j)是否構(gòu)成一個Palindrome
轉(zhuǎn)移方程：
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
初始化：
dp[i][j] = true when j - i <= 2
結(jié)果：
找 maxLen = j - i + 1;，并得到相應(yīng)longest substring： longest = s.substring(i, j + 1);

中心擴(kuò)展

這種方法基本思想是遍歷數(shù)組，以其中的1個元素或者2個元素作為palindrome的中心，通過輔助函數(shù)，尋找能拓展得到的最長子字符串。外層循環(huán) O(n)，內(nèi)層循環(huán)O(n)，因此時間復(fù)雜度 Time O(n^2)，相比動態(tài)規(guī)劃二維數(shù)組存狀態(tài)的方法，因?yàn)橹恍枰孀铋Lpalindrome子字符串本身，這里空間更優(yōu)化：Space O(1)。

三、解題代碼

區(qū)間DP，Time O(n^2) Space O(n^2)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
     public String longestPalindrome(String s) {
         if(s == null || s.length() <= 1) {
             return s;
         }

         int len = s.length();
         int maxLen = 1;
         boolean [][] dp = new boolean[len][len];

         String longest = null;
         for(int k = 0; k < s.length(); k++){
             for(int i = 0; i < len - k; i++){
                 int j = i + k;
                 if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
                     dp[i][j] = true;

                     if(j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        longest = s.substring(i, j + 1);
                     }
                 }
             }
         }

         return longest;
     }
}

Time O(n^2) Space O(1)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
            if (s.isEmpty()) {
                return null;
            }

            if (s.length() == 1) {
                return s;
            }

            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                // get longest palindrome with center of i
                String tmp = helper(s, i, i);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }

                // get longest palindrome with center of i, i+1
                tmp = helper(s, i, i + 1);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }
            }

            return longest;
    }

    // Given a center, either one letter or two letter,
    // Find longest palindrome
    public String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        return s.substring(begin + 1, end);
    }
}

下一篇: 8. DP_01背包問題整理
上一篇: 6. DP_Maximum product Subarray