最长回文子串-LeetCode5 动态规划

由于基础还不是很牢固 一时间只能想到暴力的解法:

取遍每个子串 总数量n+n-1+n-2+…+1 =O(n^2)
判断每个子串是否属于回文串 O(n)
故总时间复杂度为O(n^3)

class Solution {
public:string longestPalindrome(string s) {
int max=0;string ret;for(int i=0;i<s.size();i++)for(int j=1;j<=s.size()-i;j++){string s1=s.substr(i,j);if(Judeg(s1)>max){max=Judeg(s1);ret=s1;}}return ret;}int Judeg(string s)
{int i,j;for(i=0,j=s.size()-1;i<=j;i++,j--){if(s[i]!=s[j])return 0;}return s.size();
}
};

在查阅题解以后 比较简单易懂的还是动态规划算法
设某子串的左下标为i 右下标为j
则该子串是不是回文串可以走如下流程:
1.s[i]和s[j]不相等 那么一定不是回文子串 dp[i][j]=false
2.在s[i]和s[j]已经相等的基础上 若子串的长度<=3 那么一定是回文串 dp[i][j]=true
3.最后一种情况 dp[i][j]=dp[i+1][j-1]
一个很长的子串是不是回文串 取决于去掉首尾字符以后 中间的子串是不是回文串(动态规划套娃)

时间复杂度为遍历dp数组 故为O(n^2)
空间复杂度为开辟dp数组 故为O(n^2)

string longestPalindrome(string s) 
{int max=1,begin=0;int len=s.size();if(len<2)return s;bool **dp=new bool*[len];for(int i=0;i<len;i++){dp[i]=new bool [len];}for(int j=1;j<len;j++){for(int i=0;i<j;i++){if(s[i]!=s[j])dp[i][j]=false;else{if(j-i+1<=3)dp[i][j]=true;else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]&&j-i+1>max){max=j-i+1;begin=i;}}}return s.substr(begin,max);
}