LeetCode OJ:Longest Palindromic Substring

本文主要是介绍LeetCode OJ:Longest Palindromic Substring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法思想：

动态规划，用时484ms

class Solution {  
public:  string longestPalindrome(string s) {  int n = s.length();  bool dp[1000][1000];  int start = 0;  int max = 1;  for (int j = 0; j < n; ++j)  {  for (int i = 0; i <= j; ++i)  {  if (( j-i<= 1 || dp[i+1][j-1]) && s[i] == s[j])  {  dp[i][j] = true;  if (j-i+1 > max)  {  start = i;  max = j-i+1;  }  }  else dp[i][j] = false;  }  }  return s.substr(start,max);  }  
};  

2、网上有人贴出了中心向外拓展的方法，也不错，用时140ms，思路挺简单，只是对奇偶个回文串需要注意

class Solution {  
public:  string longestPalindrome(string s) {  size_t n = s.length();  int startPos = 0;  int max = 1;  for (int i = 0; i < n; ++i)  {  int oddLen = 0, evenLen = 0, curLen;  oddLen = Palindromic(s,i,i);  if (i + 1 < n)  evenLen = Palindromic(s,i,i+1);  curLen = oddLen > evenLen? oddLen : evenLen;  if (curLen > max)  {  max = curLen;  if (max & 0x1)  startPos = i - max / 2;  else   startPos = i - (max - 1) / 2;  }  }  return s.substr(startPos,max);  }  int Palindromic(const string &str, int i, int j)  {  size_t n = str.length();  int curLen = 0;  while (i >= 0 && j < n && str[i] == str[j])  {  --i;  ++j;  }  curLen = (j-1) - (i+1) + 1;  return curLen;  }  
};  

3、网上有人贴出用KMP算法实现的解答 最长连续回文串（Longest Palindromic Substring）

我将java版的改成c++版的并优化了下，算法是可以的，但是还是TLE

class Solution {  int *nextval;
public:  void get_nextval(char const* ptrn, int plen, int* nextval)        {        int i = 0;         nextval[i] = -1;        int j = -1;        while( i < plen-1 )        {        if( j == -1 || ptrn[i] == ptrn[j] )       {        ++i;        ++j;        if( ptrn[i] != ptrn[j] )         nextval[i] = j;              else        nextval[i] = nextval[j];        }        else                                         j = nextval[j];        }        }    int KMP(const char *S, const char *T) {    int slen = strlen(S);    int tlen = strlen(T);    int i = 0 ,j = 0;    int maxLen=0;//int *nextval=new int[tlen];    get_nextval(T,tlen,nextval);    while ( i+j < slen && j < tlen){    if ( j == -1 || S[i+j] == T[j] ){    j ++;    }    else    {    i ++;    j = nextval[j];    }    if( j > maxLen)  {  maxLen = j;  }  if(j == tlen)  {  return maxLen;  }  }    return maxLen;   } string longestPalindrome(string s) {  string str=s;const char *S=str.c_str();int size=s.length();reverse(s.begin(),s.end());  //求得到 输入string 的reverse  nextval = new int[1000];  int start = 0;  int maxLen = 0;  int len;  for(int i = 0; i < size; i++) //枚举所有后缀  {    if( size - i < maxLen)  {  break;  }  len = KMP(S, &s[i]);  if( len > maxLen)  {  start = i; maxLen = len;  }  }  return s.substr(start,maxLen);  }  
};  

思路4. 算法来源于此

http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

不过原文的陈述仔细研究了一下，有一些地方让人着实费解，所以自己决定重写一遍。

这里描述了一个叫Manacher’s Algorithm的算法。

算法首先将输入字符串S， 转换成一个特殊字符串T，转换的原则就是将S的开头结尾以及每两个相邻的字符之间加入一个特殊的字符，例如#

例如: S = “abaaba”, T = “#a#b#a#a#b#a#”.

为了找到最长的回文字串，例如我们当前考虑以Ti为回文串中间的元素，如果要找到最长回文字串，我们要从当前的Ti扩展使得 T_i-d … T_i+d 组成最长回文字串. 这里 d 其实和 以Ti为中心的回文串长度是一样的. 进一步解释就是说，因为我们这里插入了 # 符号，对于一个长度为偶数的回文串，他应该是以#做为中心的，然后向两边扩，对于长度是奇数的回文串，它应该是以一个普通字符作为中心的。通过使用#，我们将无论是奇数还是偶数的回文串，都变成了一个以Ti为中心，d为半径两个方向扩展的问题。并且d就是回文串的长度。

例如 #a#b#a#, P = 0103010, 对于b而言P的值是3，是最左边的#，也是延伸的最左边。这个值和当前的回文串是一致的。

如果我们求出所有的P值，那么显然我们要的回文串，就是以最大P值为中心的回文串。

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

例如上面的例子，最长回文是 “abaaba”, P₆ = 6.

根据观察发现，如果我们在一个位置例如 abaaba的中间位置，用一个竖线分开，两侧的P值是对称的。当然这个性质不是在任何时候都会成立，接下来就是分析如何利用这个性质，使得我们可以少算很多P的值。

下面的例子 S = “babcbabcbaccba” 存在更多的折叠回文字串。

当时当i = 15的时候，却只能得到回文 “a#b#c#b#a”, 长度是5， 而对称 i ' = 7 的长度是7. 

扩充P[i] 之后，我们还要做一件事情是更新 R 和 C， 如果当前对称中心的最右延伸大于R，我们就更新C和R。在迭代的过程中，我们试探i的时候，如果P[i'] <= R - i, 那么只要做一件事情。 如果不成立我们对当前P[i] 做扩展，因为最大长度是n，扩展最多就做n次，所以最多做2*n。 所以最后算法复杂度是 O(n)

这篇关于LeetCode OJ:Longest Palindromic Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---