文章目录

LeetCode正题

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"

思考

回文字符串即正向顺序和反向顺序的字幕排序是一致的字段串。题的大意为寻找一个指定字符串中的最长的回文字符串。
首选,暴力解法需要遍历所有子串并判断子串是否为回文字符串。假设给定字符串长度n,那么子串的总数为​n(n+1)/2(即1 2 3 … n的和),即需要O(n^2),然后判断每个子串是否为回文字符串的时间复杂度为O(n),即总共需要时间复杂度O(n^3)。时间肯定会超时的。
其中,上面暴力解法中的“判断子串是否为回文字符串”的时间复杂度可以优化到O(1)的。即利用动态规划思想,损耗O(n^2)的空间。
声明一个二维数组int dp[][],第一维表示子串的起始索引下标,第二维表示子串的结束索引下标,值为能区分是否为回文字符串的标志即可。判断当前子串是否为“回文字符串”的判断依据即,当前子串的首位字符相等,且舍去首位字符的子串也为“回文字符串”即可。这样,可以把判断子串是否为回文字符串的时间缩减到常量时间。即可以达到整体是时间复杂度为O(n^2)。
状态转移方程:
dp[s][e] = dp[s+1][e-1] && s[s] == s[e]

代码

[code lang=”cpp”]
/**
* https://leetcode.com/problems/longest-palindromic-substring/solution/
*
* this demo:using the dp method, time O(n^2) space O(n^2)
*
*/
#include <iostream>
#include <vector>
#include <map>
#include <string>

#define MAX 1001

using namespace std;

class Solution {
private:
string str;

public:
string longestPalindrome(string os) {
str = os; // os:original string
int dp[MAX][MAX] = {0};
int ml = 0, ofs = 0, l = str.length(); // ml:max length ofs:offset
for (int i = 0; i < l; ++i) {
for (int j = i; j < l; ++j) {
if (isPalindrome(i, j, dp)) {
if (j – i + 1> ml) {
ofs = i;
ml = j – i + 1;
}
}
}
}
return str.substr(ofs, ml);
}

private :
bool isPalindrome(int s, int e, int dp[MAX][MAX]) { // s:start e:end
if (dp[s][e] == 0) {
switch (e – s + 1) {
case 1:
dp[s][e] = -1;
break;
case 2:
dp[s][e] = str[s] == str[e] ? -1 : -2;
break;
default:
dp[s][e] = (str[s] == str[e] && isPalindrome(s + 1, e – 1, dp))? -1 : -2;
}
}
return dp[s][e] == -1 ? true : false;
}
};

int main(int argc, char * argv[]) {
Solution * s = new Solution();
cout<<s->longestPalindrome("vommleztyrbrnoij");
}

[/code]

结束语

当然,还可以将空间复杂度优化到O(1)(没有看懂,传送门 => Approach #4 (Expand Around Center) [Accepted]),时间复杂到优化到O(n)(利用Manacher算法,传送门 => Approach #5 (Manacher’s Algorithm) [Accepted])。

 


参考文章:https://leetcode.com/problems/longest-palindromic-substring/solution/#approach-5-manachers-algorithm-accepted

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.