首页 > 代码库 > Leetcode | Longest Palindromic Substring

Leetcode | Longest Palindromic Substring

2024-07-04 07:17:22   230人阅读

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Method I

之前先做了Palindrome Partitioning，所以一开始也用二维动态规划来做，vector<vector<int> > 报MLE。

然后又用和Minimum Window Substring同样的思路，在[0...i]找包含s[i]的最长回文串，最后再求最大。

在找包含s[i]的最长回文串时，首先保存了包含s[i-1]的最长回文串的长度pre，如果s[i]=s[i - pre - 1]，那么从s[i-pre-1...i]是回文串，包含s[i]的最长回文串长度就是pre+2。

如果s[i]!=s[i - pre - 1]，那么就从i - pre开始找包含s[i]的最长回文串。

最后取最长的回文串。算法复杂度O(n^2)。空间复杂度O(1)。

 1 class Solution {
 2 public:
 3     
 4     bool isPalindrome(string &str, int s, int e) {
 5         while (s <= e) {
 6             if (str[s] != str[e]) return false;
 7             s++;
 8             e--;
 9         }
10         return true;
11     }
12     
13     string longestPalindrome(string s) {
14         int n = s.length();
15         if (n <= 1) return s;
16         
17         int max = 1, start = 0, pre = 0;
18         for (int i = 1; i < n; ++i) {
19             int j = i - pre - 1;
20             if (s[i] == s[j]) {
21                 pre += 2;
22             } else {
23                 for (j++; j <= i; ++j) {
24                     if (isPalindrome(s, j, i)) {
25                         pre = i - j + 1;
26                         break;
27                     }
28                 }
29             }
30             if (pre > max) {
31                 max = pre;
32                 start = j;
33             }
34         }
35         return s.substr(start, max);
36     }
37 };

 Method II

以下摘自http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

二维dp。时间复杂度O(n^2)。空间复杂度O(n^2)。用table[1000][1000]就能通过，用vector<vector<int> > 报MLE，用vector<vector<bool> >报TLE。看来以后dp还是用数组来做快些。 

这里dp的构建过程和平常不一样，不是一个位置一个位置移动去构建，而是按长度来构建。len=1,2,....

 1 string longestPalindromeDP(string s) {
 2   int n = s.length();
 3   int longestBegin = 0;
 4   int maxLen = 1;
 5   bool table[1000][1000] = {false};
 6   for (int i = 0; i < n; i++) {
 7     table[i][i] = true;
 8   }
 9   for (int i = 0; i < n-1; i++) {
10     if (s[i] == s[i+1]) {
11       table[i][i+1] = true;
12       longestBegin = i;
13       maxLen = 2;
14     }
15   }
16   for (int len = 3; len <= n; len++) {
17     for (int i = 0; i < n-len+1; i++) {
18       int j = i+len-1;
19       if (s[i] == s[j] && table[i+1][j-1]) {
20         table[i][j] = true;
21         longestBegin = i;
22         maxLen = len;
23       }
24     }
25   }
26   return s.substr(longestBegin, maxLen);
27 }

Method III

从中心扩展的方法。时间复杂度O(n^2)。空间复杂度O(1)。

 1 string expandAroundCenter(string s, int c1, int c2) {
 2   int l = c1, r = c2;
 3   int n = s.length();
 4   while (l >= 0 && r <= n-1 && s[l] == s[r]) {
 5     l--;
 6     r++;
 7   }
 8   return s.substr(l+1, r-l-1);
 9 }
10  
11 string longestPalindromeSimple(string s) {
12   int n = s.length();
13   if (n == 0) return "";
14   string longest = s.substr(0, 1);  // a single char itself is a palindrome
15   for (int i = 0; i < n-1; i++) {
16     string p1 = expandAroundCenter(s, i, i);
17     if (p1.length() > longest.length())
18       longest = p1;
19  
20     string p2 = expandAroundCenter(s, i, i+1);
21     if (p2.length() > longest.length())
22       longest = p2;
23   }
24   return longest;
25 }

Method VI

 非常巧妙的方法。看了解释之后理解还是有些困难。

思路大概是这样子：

首先把原串S每两个字符之间插入一个#，存为T。这样做的好处是可以无差别地处理奇数和偶数的palindrome串。

如图，维护一个palindrome区间，[L,R]，以C作为中心。可以看到数组p就是以每个位置为中心的palindrome串的长度。

i和i‘关于C成镜像，也就是i‘=C*2-i。

如果i>=R，P[i]=0.

否则，如果P[i‘]<=R-i，那么P[i]=P[i‘]，对称的；

如果P[i‘]>R-i，那么我们的是就要尝试扩展一下R；

如果成功扩展了，也就是i+P[i]>R，那么就移动中心C，C=i，扩展R=i+P[i]；

最后再求一下P的最大值；

 1 // Transform S into T.
 2 // For example, S = "abba", T = "^#a#b#b#a#$".
 3 // ^ and $ signs are sentinels appended to each end to avoid bounds checking
 4 string preProcess(string s) {
 5   int n = s.length();
 6   if (n == 0) return "^$";
 7   string ret = "^";
 8   for (int i = 0; i < n; i++)
 9     ret += "#" + s.substr(i, 1);
10  
11   ret += "#$";
12   return ret;
13 }
14  
15 string longestPalindrome(string s) {
16   string T = preProcess(s);
17   int n = T.length();
18   int *P = new int[n];
19   int C = 0, R = 0;
20   for (int i = 1; i < n-1; i++) {
21     int i_mirror = 2*C-i; // equals to i‘ = C - (i-C)
22     
23     P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
24     
25     // Attempt to expand palindrome centered at i
26     while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
27       P[i]++;
28  
29     // If palindrome centered at i expand past R,
30     // adjust center based on expanded palindrome.
31     if (i + P[i] > R) {
32       C = i;
33       R = i + P[i];
34     }
35   }
36  
37   // Find the maximum element in P.
38   int maxLen = 0;
39   int centerIndex = 0;
40   for (int i = 1; i < n-1; i++) {
41     if (P[i] > maxLen) {
42       maxLen = P[i];
43       centerIndex = i;
44     }
45   }
46   delete[] P;
47   
48   return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
49 }

Line 26-27内循环，可以看作是扩展R的步骤，R在整个代码中是只增不减的，总的最多扩展n步，所以整个算法是2n的开销，时间复杂度为O(n)，空间复杂度也是O(n)。

事后诸葛

对于这类，要求某个最优区间的。可以考虑：

1. 和Minimum Window Substring同样的思路，在[0...i]找包含s[i]的最优区间。然后再取最优；

2. 也可以尝试Method II，二维动态规划，构建的时候以区间长度来构建。


联系
我们