給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
示例 2：輸入: "cbbd"
輸出: "bb"
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
動(dòng)態(tài)規(guī)劃，但是時(shí)間復(fù)雜度O(n^2)，勉強(qiáng)跑過
class Solution {
private static final String EMPTY = "";
/**
* 動(dòng)態(tài)規(guī)劃
*
* 1. 狀態(tài)定義
* f(x) = 以x元素坐標(biāo)為中心的回文
* 2. 狀態(tài)轉(zhuǎn)移方程
* f(x) = f(2 * x - i) + f(x) + f(i), x = 0 ~ i
*
* 時(shí)間復(fù)雜度O(n^2)，此解超時(shí)
*
* @param s
* @return
*/
public String longestPalindrome(String s) {
int len = s.length();
// 加上這個(gè)判斷勉強(qiáng)跑過了
if (len == 0 || s.replace(String.valueOf(s.charAt(0)), "").length() == 0) {
return s;
}
String[] palindrome = new String[2 * len + 1];
String max = "";
for (int i = 0; i < 2 * len + 1; i++) {
char iCh = getChar(s, i);
setChar(palindrome, s, i);
for (int j = 0; j <= i; j++) {
int before = 2 * j - i;
if (before < 0 || getChar(s, before) != iCh || !needPalindrome(j, i, palindrome[j])) {
continue;
}
palindrome[j] = iCh + (palindrome[j] == null ? "" : palindrome[j]) + iCh;
if (palindrome[j].length() > max.length()) {
max = palindrome[j];
}
}
}
return max.replace(String.valueOf(Character.MIN_VALUE), "");
}
/**
* 只有連續(xù)的元素是回文才能算是回文
*
* @param position 回文中心
* @param index 最外的字符
* @param palindrome 當(dāng)前的回文
* @return
*/
private boolean needPalindrome(int position, int index, String palindrome) {
int curLen = palindrome == null ? 0 : palindrome.length();
return index - position == curLen / 2 + 1;
}
/**
* index是填充后的坐標(biāo)，s是為填充的字符串，獲取對(duì)應(yīng)的字符需要進(jìn)行轉(zhuǎn)換
*
* @param s
* @param index
* @return
*/
private char getChar(String s, int index) {
if (index % 2 == 0) {
return Character.MIN_VALUE;
}
return s.charAt(index / 2);
}
private void setChar(String[] palindrome, String s, int index) {
if (index % 2 == 0) {
palindrome[index] = EMPTY;
} else {
palindrome[index] = String.valueOf(s.charAt(index / 2));
}
}
}
運(yùn)行效率
動(dòng)態(tài)規(guī)劃v2
class Solution {
/**
* 動(dòng)態(tài)規(guī)劃
*
* 1. 狀態(tài)定義
* f[begin][end]: 坐標(biāo)i到j(luò)字符串是否是回文
*
* 2. 狀態(tài)轉(zhuǎn)移方程
* f[begin][end] = f[begin+1][end-1] && (s[begin] == s[end]), (begin <= end)
*
* @param s
* @return
*/
public String longestPalindrome(String s) {
if (s.length() == 0) {
return s;
}
int maxLen = 1, maxLeft = 0, maxRight = 0;
boolean[][] f = new boolean[s.length()][s.length()];
// 初始狀態(tài)
for (int i = 0; i < s.length(); i++) {
// 單個(gè)元素都是回文
f[i][i] = true;
}
for (int end = 1; end < s.length(); end++) {
for (int begin = 0; begin < end; begin++) {
if (s.charAt(begin) != s.charAt(end)) {
continue;
}
if (end - begin < 3 || f[begin + 1][end - 1]) {
f[begin][end] = true;
if (end - begin + 1 > maxLen) {
maxLen = end - begin + 1;
maxLeft = begin;
maxRight = end;
}
}
}
}
return s.substring(maxLeft, maxRight + 1);
}
}
運(yùn)行效率
類似動(dòng)態(tài)規(guī)劃，比較優(yōu)的O(n^2)算法
class Solution {
private int maxLen = 1; // 最大長度
private int resLeft = 0;
private int resRight = 0;
/**
* 分別以每個(gè)節(jié)點(diǎn)為中心進(jìn)行擴(kuò)散，記錄最大的回文
*
* @param s
* @return
*/
public String longestPalindrome(String s) {
if (s.length() == 0) {
return s;
}
for (int i = 0; i < s.length(); i++) {
// 以i為中心，奇數(shù)元素的回文
searchPalindrome(s, i - 1, i + 1);
// 以i和i+1為中心，偶數(shù)元素的回文
searchPalindrome(s, i, i + 1);
}
return s.substring(resLeft, resRight + 1);
}
private void searchPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > maxLen) {
maxLen = right - left - 1;
resLeft = left + 1;
resRight = right - 1;
}
}
}
運(yùn)行效率
