Fetching contributors…
Cannot retrieve contributors at this time
162 lines (106 sloc) 6.14 KB

# Longest Palindromic Substring

## Description

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"
``````

Tags: String, Dynamic Programming

## 思路 0

```class Solution {
int st, end;

public String longestPalindrome(String s) {
int len = s.length();
if (len <= 1) return s;
char[] chars = s.toCharArray();
for (int i = 0; i < len; i++) {
helper(chars, i, i);
helper(chars, i, i + 1);
}
return s.substring(st, end + 1);
}

private void helper(char[] chars, int l, int r) {
while (l >= 0 && r < chars.length && chars[l] == chars[r]) {
--l;
++r;
}
if (end - st < r - l - 2) {
st = l + 1;
end = r - 1;
}
}
}```

## 思路 1

1. `i == j` 时，那么毫无疑问 `dp[i][j] = true`

2. `i + 1 == j` 时，那么 `dp[i][j]` 的值取决于 `s[i] == s[j]`

3. `i + 1 < j` 时，那么 `dp[i][j]` 的值取决于 `dp[i + 1][j - 1] && s[i] == s[j]`

```class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len <= 1) return s;
int st = 0, end = 0;
char[] chars = s.toCharArray();
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
for (int j = 0; j < i; j++) {
if (j + 1 == i) {
dp[j][i] = chars[j] == chars[i];
} else {
dp[j][i] = dp[j + 1][i - 1] && chars[j] == chars[i];
}
if (dp[j][i] && i - j > end - st) {
st = j;
end = i;
}
}
}
return s.substring(st, end + 1);
}
}```

## 思路 2

### 背景

1. s = "babad"，最长回文长度为 `3`，可以是 `bab` 或者 `aba`

2. s = "cbbda"，最长回文长度为 `2`，即 `bb`

3. s = "abcde"，最长回文长度为 `1`，即单个字符本身。

1975 年，一个叫 Manacher 的人发明了 Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 `O(n)`，下面我以我理解的思路来讲解其原理。

### 分析

``````lol  -> #l#o#l#
lool -> #l#o#o#l#
``````

str # l # o # l # l # o # o # l #
len[] 1 2 1 4 l 2 5 2 1 2 5 2 1 2 1

## 结语

You can’t perform that action at this time.