题目描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example2:
Input: “cbbd”
Output: “bb”
dp 时间复杂度 O(n^2)
- 动态规划 Dynamic Programming 来解，
- 根 Palindrome Partitioning II 的解法很类似，我们维护一个二维数组 dp，
- 其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串，
- 当 i = j 时，只有一个字符，肯定是回文
- 如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]
- 如果i和j不相邻，即 i - j >= 2 时，除了判断 s[i] 和 s[j] 相等之外，dp[i + 1][j - 1] 若为真，就是回文串，通过以上分析，可以写出递推式如下：
dp[i, j] = 1 (if i == j)
= s[i] == s[j] (if j = i + 1)
= s[i] == s[j] && dp[i + 1][j - 1] (if j > i + 1)
class Solution {
public:
int isPalindRomic(string s, int start, int end){
for(; start < end; start++, end--){
if(s[start] != s[end]){
return 0;
}
}
return 1;
}
string longestPalindrome(string s) {
int start = 0, i, j;
int len = s.size(), maxLen = 1;
if(len == 0){
return "";
}
int dp[len][len] = {0};
for(int i = 0; i < len; i++){
dp[i][i] = 1;
}
for(int i = 0; i < len; i++){
for(int j = 0; j < i; j++){
dp[j][i] = (s[j] == s[i] && ((i - j < 2 || dp[j + 1][i - 1]))); // 线段 j在前面，i在后面[j, i]区间判断
if(dp[j][i] && maxLen < i - j + 1){ // 长度应该是 i - j + 1
maxLen = i - j + 1;
start = j;
}
}
}
return s.substr(start, maxLen);
}
};
不能AC的版 TLE
- 暴力
- 首先写一个函数，查看这个字符串是否为回文
- 然后两次遍历即可
- 时间复杂度为 o(n^3)
class Solution {
public:
int isPalindRomic(string s, int start, int end){
for(; start < end; start++, end--){
if(s[start] != s[end]){
return 0;
}
}
return 1;
}
string longestPalindrome(string s) {
int start = 0, i, j;
int len = s.size(), maxLen = 1;
for(int i = 0; i < len - 1; i++){
for(int j = i + 1; j < len; j++){
if(isPalindRomic(s, i, j)){
int t = j - i + 1;
if(t > maxLen){
maxLen = t;
start = i;
}
}
}
}
return s.substr(start, maxLen);
}
};
不能AC的版 WRONG ANSWER
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n == 1){
return s;
}
string res;
int len = 0;
for(int i = 0; i < n; i++){
string temp = "";
// temp += s[i];
for(int j = i; j < n; j++){
temp = temp + s[j];
if(isPalindRomic(temp) && temp.size() > len){
len = s.size();
res = temp;
}
}
}
return res;
}
bool isPalindRomic(string s){
int n = s.size();
if(n == 1){
return true;
}
for(int i = 0; i < s.size() / 2; i++){
if(s[i] != s[n - i - 1]){
return false;
}
}
return true;
}
};
