一、说明
“回文串”是一个正读和反读都一样的字符串。
给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
二、解决方案参考
1. Swift 语言
class LongestPalindromicSubstring {
func longestPalindrome(_ s: String) -> String {
guard s.characters.count > 1 else {
return s
}
var sChars = [Character](s.characters)
let len = sChars.count
var maxLen = 1
var maxStart = 0
var isPalin = Array(repeating: Array(repeating: false, count : len), count : len)
// set palindrome whose len is 1
for i in 0...len - 1 {
isPalin[i][i] = true
}
// set palindrome whose len is 2
for i in 0...len - 2 {
if sChars[i] == sChars[i + 1] {
isPalin[i][i + 1] = true
maxLen = 2
maxStart = i
}
}
if len >= 3 {
for length in 3...len {
for i in 0...len - length {
if sChars[i] == sChars[i + length - 1] && isPalin[i + 1][i + length - 2] {
isPalin[i][i + length - 1] = true
maxLen = length
maxStart = i
}
}
}
}
return String(sChars[maxStart...maxStart + maxLen - 1])
}
}2. JavaScript 语言
/**
* @param {string} s
* @return {string}
*/
// return the Longest Palindromic Substring of s
function Manacher(s) {
var str = '*#'
, dp = []
, maxn = 0
, idx = 0;
for (var i = 0, len = s.length; i < len; i++)
str += s[i] + '#';
for (var i = 1, len = str.length; i < len; i++) {
if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);
else dp[i] = 1;
while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;
if (dp[i] + i > maxn)
maxn = dp[i] + i, idx = i;
}
var ans = 0
, pos;
for (var i = 1; i < len; i++) {
if (dp[i] > ans)
ans = dp[i], pos = i;
}
var f = str[pos] === '#'
, tmp = f ? '' : str[pos]
, startPos = f ? pos + 1 : pos + 2
, endPos = f ? dp[pos] - 3 + startPos : dp[pos] - 4 + startPos;
for (var i = startPos; i <= endPos; i += 2)
tmp = str[i] + tmp + str[i];
return tmp;
}
var longestPalindrome = function(s) {
var str = Manacher(s);
return str;
};3. Python 语言
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
left = right = 0
n = len(s)
for i in range(n - 1):
if 2 * (n - i) + 1 < right - left + 1:
break
l = r = i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r - l - 2 > right - left:
left = l + 1
right = r - 1
l = i
r = i + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r - l - 2 > right - left:
left = l + 1
right = r - 1
return s[left:right + 1]4. Java 语言
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}5. C++ 语言
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string findPalindrome(string s, int left, int right)
{
int n = s.size();
int l = left;
int r = right;
while (left>=0 && right<=n-1 && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left+1, right-left-1);
}
// This is the common solution.
// Actuatlly it's faster than DP solution under Leetcode's test
// the below optimized DP solution need 700ms+, this needs around 250ms.
string longestPalindrome_recursive_way(string s) {
int n = s.size();
if (n<=1) return s;
string longest;
string str;
for (int i=0; i<n-1; i++) {
str = findPalindrome(s, i, i);
if (str.size() > longest.size()){
longest = str;
}
str = findPalindrome(s, i, i+1);
if (str.size() > longest.size()){
longest = str;
}
}
return longest;
}
//================================================================================
void findPalindrome(string s, int left, int right, int& start, int& len)
{
int n = s.size();
int l = left;
int r = right;
while (left>=0 && right<=n-1 && s[left] == s[right]) {
left--;
right++;
}
if (right-left-1 > len){
len = right-left-1;
start = left+1;
}
}
//The following solution is better than previous solution.
//Because it remove the sub-string return in findPalindrome().
string longestPalindrome_recursive_way2(string s) {
int n = s.size();
if (n<=1) return s;
int start=0, len=0;
string longest;
string str;
for (int i=0; i<n-1; i++) {
findPalindrome(s, i, i, start, len);
findPalindrome(s, i, i+1, start, len);
}
return s.substr(start, len);
}
//================================================================================
// Time/Memory Limit Exceeded
string longestPalindrome_dp_way(string s) {
string longest;
int n = s.size();
if (n<=1) return s;
//Construct a matrix, and consdier matrix[i][j] as s[i] -> s[j] is Palindrome or not.
//using char or int could cause the `Memory Limit Error`
//vector< vector<char> > matrix (n, vector<char>(n));
//using bool type could cause the `Time Limit Error`
vector< vector<bool> > matrix (n, vector<bool>(n));
// Dynamic Programming
// 1) if i == j, then matrix[i][j] = true;
// 2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i+1][j-1])
for (int i=n-1; i>=0; i--){
for (int j=i; j<n; j++){
// The following if statement can be broken to
// 1) i==j, matrix[i][j] = true
// 2) the length from i to j is 2 or 3, then, check s[i] == s[j]
// 3) the length from i to j > 3, then, check s[i]==s[j] && matrix[i+1][j-1]
if ( i==j || (s[i]==s[j] && (j-i<2 || matrix[i+1][j-1]) ) ) {
matrix[i][j] = true;
if (longest.size() < j-i+1){
longest = s.substr(i, j-i+1);
}
}
}
}
return longest;
}
// Optimized DP soltuion can be accepted by LeetCode.
string longestPalindrome_dp_opt_way(string s) {
int n = s.size();
if (n<=1) return s;
//Construct a matrix, and consdier matrix[j][i] as s[i] -> s[j] is Palindrome or not.
// ------^^^^^^
// NOTE: it's [j][i] not [i][j]
//Using vector could cause the `Time Limit Error`
//So, use the native array
bool **matrix = (bool**)malloc(n*sizeof(bool*));
int start=0, len=0;
// Dynamic Programming
// 1) if i == j, then matrix[i][j] = true;
// 2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i-1][j+1])
for (int i=0; i<n; i++){
matrix[i] = (bool*)malloc((i+1)*sizeof(bool));
memset(matrix[i], false, (i+1)*sizeof(bool));
matrix[i][i]=true;
for (int j=0; j<=i; j++){
// The following if statement can be broken to
// 1) j==i, matrix[i][j] = true
// 2) the length from j to i is 2 or 3, then, check s[i] == s[j]
// 3) the length from j to i > 3, then, check s[i]==s[j] && matrix[i-1][j+1]
if ( i==j || (s[j]==s[i] && (i-j<2 || matrix[i-1][j+1]) ) ) {
matrix[i][j] = true;
if (len < i-j+1){
start = j;
len = i-j+1;
}
}
}
}
for (int i=0; i<n; i++) {
free (matrix[i]);
}
free(matrix);
return s.substr(start, len);
}
string longestPalindrome(string s) {
return longestPalindrome_dp_way(s);
return longestPalindrome_dp_opt_way(s);
return longestPalindrome_recursive_way2(s);
return longestPalindrome_recursive_way(s);
}
int main(int argc, char**argv)
{
string s = "abacdfgdcaba";
if (argc > 1){
s = argv[1];
}
cout << s << " : " << longestPalindrome(s) << endl;
s = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123";
cout << s << " : " << longestPalindrome(s) << endl;
//"illi"
s = "iptmykvjanwiihepqhzupneckpzomgvzmyoybzfynybpfybngttozprjbupciuinpzryritfmyxyppxigitnemanreexcpwscvcwddnfjswgprabdggbgcillisyoskdodzlpbltefiz";
cout << s << " : " << longestPalindrome(s) << endl;
return 0;
}
6. C 语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static inline int min(int a, int b)
{
return a < b ? a : b;
}
static int manacher(char *s, char output[])
{
int i, j;
char s2[3000] = { '\0' };
s2[0] = '$';
for (i = 0; s[i] != '\0'; i++) {
s2[(i<<1)+1] = '#';
s2[(i<<1)+2] = s[i];
}
s2[(i<<1)+1] = '#';
int len = (i<<1)+2;
s2[len] = '\0';
int p[3000] = { 0 }; // 以s2中某一点为中心的回文半径
int id = 0; // 回文的中心点
int limit = 0; // 最长回文的右边界点
int maxLen = 0; // 最大回文长度
int maxId = 0; // 最长回文的中心点
for (i = 1; i < len; i++) {
if (i < limit) {
p[i] = min(p[2*id-i], limit-i);
} else {
p[i] = 1;
}
while (s2[i+p[i]] == s2[i-p[i]]) {
p[i]++;
}
if (i+p[i] > limit) {
limit = i+p[i];
id = i;
}
if (maxLen < p[i]-1) {
maxLen = p[i]-1;
maxId = i;
}
}
for (j = 0, i = maxId - maxLen; i <= maxId+maxLen; i++) {
if (s2[i] != '#') {
output[j++] = s2[i];
}
}
return maxLen;
}
static char *longestPalindrom(char *s)
{
int i;
if (s == NULL) {
return NULL;
}
int len = strlen(s);
if (len <= 1) {
return s;
}
char *palindrome = malloc(2000);
memset(palindrome, 0, sizeof(palindrome));
int size = manacher(s, palindrome);
palindrome[size] = '\0';
return palindrome;
}
int main(int argc, char **argv)
{
if (argc != 2) {
fprintf(stderr, "Usage: ./test string
");
exit(-1);
}
printf("%s
", longestPalindrom(argv[1]));
return 0;
}
--------------------------------------
版权声明：本文为【PythonJsGo】博主的原创文章，转载请附上原文出处链接及本声明。
博主主页：https://my.oschina.net/u/3375733
本篇文章同步在个人公众号：
