湖南网站推,wordpress主题windows,网站开发 打标签,兰溪网站建设由于基础还不是很牢固 一时间只能想到暴力的解法:
取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3)
class Solution {
public:string longestPalindrome(string s) {
int max0;string ret;for(int i0;is.size();i)for(int…
由于基础还不是很牢固 一时间只能想到暴力的解法:
取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3)
class Solution {
public:string longestPalindrome(string s) {
int max0;string ret;for(int i0;is.size();i)for(int j1;js.size()-i;j){string s1s.substr(i,j);if(Judeg(s1)max){maxJudeg(s1);rets1;}}return ret;}int Judeg(string s)
{int i,j;for(i0,js.size()-1;ij;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[i1][j-1] 一个很长的子串是不是回文串 取决于去掉首尾字符以后 中间的子串是不是回文串(动态规划套娃)
时间复杂度为遍历dp数组 故为O(n^2) 空间复杂度为开辟dp数组 故为O(n^2)
string longestPalindrome(string s)
{int max1,begin0;int lens.size();if(len2)return s;bool **dpnew bool*[len];for(int i0;ilen;i){dp[i]new bool [len];}for(int j1;jlen;j){for(int i0;ij;i){if(s[i]!s[j])dp[i][j]false;else{if(j-i13)dp[i][j]true;else{dp[i][j]dp[i1][j-1];}}if(dp[i][j]j-i1max){maxj-i1;begini;}}}return s.substr(begin,max);
}
