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"
思考
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]）。