搞暴力算法也能搞出来,而且不大困难,这个题最主要的问题是第一次接触了动态规划的东西,具有一定的历史意义。下面先贴暴力代码
class Solution { public: string longestPalindrome(string s) { int n = s.length(); int i = 0; int j = n-1; int maxSize = 1; string maxString = s.substr(0,1); for(i = 0 ; i < n-1 ; i++) { for(j = n-1 ; j > i ; j--) { if(s[i] == s[j]) { int k = 0; while(s[i+k] == s[j-k] && i+k<j-k) { k++; } if(i+k == j-k || i+k == j-k+1) { if(i == 0 && j == n-1) return s; else if(j-i+1 > maxSize) { maxSize = j-i+1; cout<<maxSize<<endl; maxString= s.substr(i,j-i+1); } } } } } return maxString; } };
下面是动态规划代码