# 5. Longest Palindromic Substring 最长回文子串

@TOC

## # 题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

``````Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
``````

Example:

``````Input: "cbbd"

Output: "bb"
``````

## # 解题方法

### # 暴力遍历

``````class Solution {
public:
string longestPalindrome(string s) {
const int N = s.size();
string res;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
if (j - i + 1 >= res.size() && isPalindrome(s, i, j)) {
res = s.substr(i, j - i + 1);
}
}
}
return res;
}
// [start, end]
bool isPalindrome(string& s, int start, int end) {
const int N = s.size();
int l = start, r = end;
while (l <= r) {
if (s[l++] != s[r--]) {
return false;
}
}
return true;
}
};
``````

### # 动态规划

1. `i = j` 时，只有一个字符，肯定是回文串；
2. 如果 `i = j + 1` ，说明是相邻字符，此时需要判断 `s[i] `是否等于 `s[j]`
3. 如果 `i``j` 不相邻，即 `i - j >= 2` 时，除了判断 `s[i]``s[j]` 相等之外，`dp[j + 1][i - 1]` 若为真，就是回文串。

``````dp[i, j] = 1                                        if i == j
= s[i] == s[j]                             if j = i + 1
= s[i] == s[j] && dp[i + 1][j - 1]         if j > i + 1
``````

Python 代码刚提交的时候超时了，但是使用set一下，看看是否只包含相同字符，这样就通过了！

``````class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(set(s)) == 1: return s
n = len(s)
start, end, maxL = 0, 0, 0
dp = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(i):
dp[j][i] = (s[j] == s[i]) & ((i - j < 2) | dp[j + 1][i - 1])
if dp[j][i] and maxL < i - j + 1:
maxL = i - j + 1
start = j
end = i
dp[i][i] = 1
return s[start : end + 1]
``````

C++版本代码如下，需要注意的是这里的res初始化为第一个字符：

``````class Solution {
public:
string longestPalindrome(string s) {
const int N = s.size();
if (N == 0) return "";
string res = s.substr(0, 1);
vector<vector<bool>> dp(N, vector(N, false));
// s[j, i]
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
dp[j][i] = (s[j] == s[i]) && (i == j + 1 || dp[j + 1][i - 1]);
if (dp[j][i] && i - j + 1 >= res.size()) {
res = s.substr(j, i - j + 1);
}
}
dp[i][i] = true;
}
return res;
}
};
``````

## # 日期

2018 年 3 月 15 日 —— 雾霾消散，春光明媚 2019 年 1 月 19 日 —— 有好几天没有更新文章了