## 题目地址

https://leetcode.com/problems/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"
``````

## 思路

• 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串
• 如果一个字符串不是回文串，或者在回文串左右分别加不同的字符，得到的一定不是回文串

``````if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
}
``````

base case 就是一个字符（轴对称点是本身），或者两个字符（轴对称点是介于两者之间的虚拟点）。

• ”延伸“（extend）

## 代码

``````/*
* @lc app=leetcode id=5 lang=javascript
*
* [5] Longest Palindromic Substring
*/
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// tag : dp
if (!s || s.length === 0) return "";
let res = s[0];

const dp = [];

// 倒着遍历简化操作， 这么做的原因是dp[i][..]依赖于dp[i + 1][..]
for (let i = s.length - 1; i >= 0; i--) {
dp[i] = [];
for (let j = i; j < s.length; j++) {
if (j - i === 0) dp[i][j] = true;
// specail case 1
else if (j - i === 1 && s[i] === s[j]) dp[i][j] = true;
// specail case 2
else if (s[i] === s[j] && dp[i + 1][j - 1]) {
// state transition
dp[i][j] = true;
}

if (dp[i][j] && j - i + 1 > res.length) {
// update res
res = s.slice(i, j + 1);
}
}
}

return res;
};
``````

### 代码 2

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n - 1; ++i) {
searchPalindrome(s, i, i, start, maxLen);
searchPalindrome(s, i, i + 1, start, maxLen);
}
return s.substr(start, maxLen);
}
void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left; ++right;
}
if (maxLen < right - left - 1) {
start = left + 1;
maxLen = right - left - 1;
}
}
};

``````

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n;) {
if (n - i <= maxLen / 2) break;
int left = i, right = i;
while (right < n - 1 && s[right + 1] == s[right]) ++right;
i = right + 1;
while (right < n - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right; --left;
}
if (maxLen < right - left + 1) {
maxLen = right - left + 1;
start = left;
}
}
return s.substr(start, maxLen);
}
};

``````

dp[i, j] = 1 if i == j

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int n = s.size(), dp[n][n] = {0}, left = 0, len = 1;
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
for (int j = 0; j < i; ++j) {
dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
if (dp[j][i] && len < i - j + 1) {
len = i - j + 1;
left = j;
}
}
}
return s.substr(left, len);
}
};

``````

``````class Solution {
public:
string longestPalindrome(string s) {
string t ="\$#";
for (int i = 0; i < s.size(); ++i) {
t += s[i];
t += '#';
}
int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
for (int i = 1; i < t.size(); ++i) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resMx < p[i]) {
resMx = p[i];
resId = i;
}
}
return s.substr((resId - resMx) / 2, resMx - 1);
}
};
``````

评论
0 评论