一块促、題目
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.
求一個(gè)字符串中的最長(zhǎng)回文子串。
二捺檬、解題思路
區(qū)間類動(dòng)態(tài)規(guī)劃
Time O(n^2), Space O(n^2)
用dp[i][j]來存DP的狀態(tài),需要較多的額外空間: Space O(n^2)
DP的4個(gè)要素
狀態(tài):
dp[i][j]: s.charAt(i)到s.charAt(j)是否構(gòu)成一個(gè)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個(gè)元素或者2個(gè)元素作為palindrome的中心,通過輔助函數(shù)交惯,尋找能拓展得到的最長(zhǎng)子字符串。外層循環(huán) O(n),內(nèi)層循環(huán)O(n)席爽,因此時(shí)間復(fù)雜度 Time O(n^2)意荤,相比動(dòng)態(tài)規(guī)劃二維數(shù)組存狀態(tài)的方法,因?yàn)橹恍枰孀铋L(zhǎng)palindrome子字符串本身只锻,這里空間更優(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