跳到主要内容

Longest Palindromic Substring

描述

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.

分析

最长回文子串,非常经典的题。

思路一:暴力枚举,以每个元素为中间元素,同时从左右出发,复杂度O(n^2)

思路二:记忆化搜索,复杂度O(n^2)。设f[i][j] 表示[i,j]之间的最长回文子串,递推方程如下:

f[i][j] = if (i == j) S[i]
if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
else max(f[i+1][j-1], f[i][j-1], f[i+1][j])

思路三:动规,复杂度O(n^2)。设状态为f(i,j),表示区间[i,j]是否为回文串,则状态转移方程为

f(i,j)={true,i=jS[i]=S[j],j=i+1S[i]=S[j] and f(i+1,j1),j>i+1f(i,j)=\begin{cases} true & ,i=j\\ S[i]=S[j] & , j = i + 1 \\ S[i]=S[j] \text{ and } f(i+1, j-1) & , j > i + 1 \end{cases}

思路四:Manacher’s Algorithm, 复杂度O(n)。详细解释见 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

备忘录法

// Longest Palindromic Substring
// 备忘录法,会超时
// 时间复杂度O(n^2),空间复杂度O(n^2)
public class Solution {
private final HashMap<Pair, String> cache = new HashMap<>();

public String longestPalindrome(final String s) {
cache.clear();
return cachedLongestPalindrome(s, 0, s.length() - 1);
}

String longestPalindrome(final String s, int i, int j) {
final int length = j - i + 1;
if (length < 2) return s.substring(i, j + 1);

final String s1 = cachedLongestPalindrome(s, i + 1, j - 1);

if (s1.length() == length - 2 && s.charAt(i + 1) == s.charAt(j - 1))
return s.substring(i, j + 1);

final String s2 = cachedLongestPalindrome(s, i + 1, j);
final String s3 = cachedLongestPalindrome(s, i, j - 1);

// return max(s1, s2, s3)
if (s1.length() > s2.length()) return s1.length() > s3.length() ? s1 : s3;
else return s2.length() > s3.length() ? s2 : s3;
}

String cachedLongestPalindrome(final String s, int i, int j) {
final Pair key = new Pair(i, j);

if (cache.containsKey(key)) {
return cache.get(key);
} else {
final String result = longestPalindrome(s, i, j);
cache.put(key, result);
return result;
}
}

// immutable
static class Pair {
private int x;
private int y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int hashCode() {
return x * 31 + y;
}

@Override
public boolean equals(Object other) {
if (this == other) return true;
if (this.hashCode() != other.hashCode()) return false;
if (!(other instanceof Pair)) return false;

final Pair o = (Pair) other;
return this.x == o.x && this.y == o.y;
}
}
}

动规

// Longest Palindromic Substring
// 动规,时间复杂度O(n^2),空间复杂度O(n^2)
class Solution {
public String longestPalindrome(final String s) {
final int n = s.length();
final boolean[][] f = new boolean[n][n];
int maxLen = 1, start = 0; // 最长回文子串的长度,起点

for (int i = 0; i < n; i++) {
f[i][i] = true;
for (int j = 0; j < i; j++) { // [j, i]
f[j][i] = (s.charAt(j) == s.charAt(i) &&
(i - j < 2 || f[j + 1][i - 1]));
if (f[j][i] && maxLen < (i - j + 1)) {
maxLen = i - j + 1;
start = j;
}
}
}
return s.substring(start, start + maxLen);
}
}

Manacher’s Algorithm

// Longest Palindromic Substring
// Manacher’s Algorithm
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
public String preProcess(final String s) {
int n = s.length();
if (n == 0) return "^$";

StringBuilder ret = new StringBuilder("^");
for (int i = 0; i < n; i++) ret.append("#" + s.charAt(i));

ret.append("#$");
return ret.toString();
}

String longestPalindrome(String s) {
String T = preProcess(s);
final int n = T.length();
// 以T[i]为中心,向左/右扩张的长度,不包含T[i]自己,
// 因此 P[i]是源字符串中回文串的长度
int[] P = new int[n];
int C = 0, R = 0;

for (int i = 1; i < n - 1; i++) {
int iMirror = 2 * C - i; // equals to i' = C - (i-C)

P[i] = (R > i) ? Math.min(R - i, P[iMirror]) : 0;

// Attempt to expand palindrome centered at i
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i]))
P[i]++;

// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}

// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}

final int start =(centerIndex - 1 - maxLen) / 2;
return s.substring(start, start + maxLen);
}
}