题目：https://leetcode-cn.com/problems/longest-palindromic-substring/
给你一个字符串 s，找到 s 中最长的回文子串。
我的方法一：动态规划
一看到最长、最优、最少等字眼，一般就是动态规划来解决。
步骤
- 确认子问题
1.1 最后一步：最大回文或者包括最后一个字符，或者不包括最后一个字符；
1.2 子问题： 加上最后一个字符后，或者最长回文还是没加最后一个字符对应的最长回文，或者是以最后一个字符为结尾的更长的回文 - 转移方程
dp[n] = max(dp[n-1], 以最后一个字符为结尾的最大回文) - 边界条件和初始条件
3.1 当字符串为空时，直接返回空
3.2 dp[n]代表的意义指以第n位字符为结尾的字符串的最大回文，所以n从0开始，最大是s.size()-1
3.3 求以最后一个字符为结尾的最大回文时，如果已经发现长度已经小于了dp[n-1]的长度，那么直接停止即可；
3.4 初始条件，dp[0] = s[0] - 计算顺序
dp[0] dp[1] dp[n]
复杂度
时间复杂度：O(nlogn)，因为需要计算n次是O(n)，另外每次查找以最后一个字符为结尾的回文复杂度是O(n)，由于需要计算的长度从0依次变为n，所以实际复杂度是O(logn)，所以总体时间复杂度是O(nlogn) = O(n)*O(logn)
空间复杂度：O(n)，因为dp数组的长度是n
代码
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 0){
return "";
}
vector<string> dp(s.size());
const char* str = s.c_str();
int size = s.size();
dp[0] = string(str, str+1);
//dp[n] = max(dp[n-1], ***);
int left = 0;
for(int i = 1; i<size; i++){
left = 0;
while(left<i){
if(isMirror(str, left, i)){
break;
}
left++;
}
if(i-left+1 > dp[i-1].size()){
dp[i] = string(str+left, str+i+1);
}else{
dp[i] = dp[i-1];
}
}
return dp[size-1];
}
private:
bool isMirror(const char* str, int left, int right){
while(left<right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
};
优化
由于dp[n]只和前一个有关，所以没有必要保留更前面的结果，所以用一个字符串保存当前的最大回文字符串即可，这样空间复杂度从O(n)降为了O(1)，实际结果从30M降到了24M。
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 0){
return "";
}
const char* str = s.c_str();
int size = s.size();
string max_loop_str = string(str, str+1);
//dp[n] = max(dp[n-1], ***);
int left = 0;
for(int i = 1; i<size; i++){
left = 0;
while(left<i){
if(isMirror(str, left, i)){
break;
}
left++;
}
if(i-left+1 > max_loop_str.size()){
max_loop_str = string(str+left, str+i+1);
}
}
return max_loop_str;
}
private:
bool isMirror(const char* str, int left, int right){
while(left<right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
};
