Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2:
Input: “cbbd” Output: “bb”
如果用单纯暴力的解法，时间复杂度为 O(n ^ 3)，肯定超时，那么就要对这个算法进行优化，这里采用的是DP思想，定义 p(i,j)为s中的第i个数到s中的第j个数的子串。
class solution { public: // 采用动态规划 i-j为字符串第i个字符到第j个字符 // 如果 i == j ，则只有一个字母 肯定是回文串 // 如果 char[i] == char[j] && j == i + 1 , 两个字母相等 肯定是回文串 // 如果 char[i] == char[j] && j > i + 1 && cache[i+1][j-1]为true，则肯定是回文串 string longestPalindrome(const string& s) { if (s.length() == 0) { return s; } int start = 0, end = 0; int len = s.length(); bool isPalindrome[10][10] = {false}; int i=0,j=0; for ( i = len-1; i >= 0; i--) { //自底向上 for ( j = i; j < len; j++) { if (i == j) { //初始化，单个字符情况 isPalindrome[i][j] = true; } else if (j == i + 1 && s[i] == s[j]) { //初始化，两个相同字符情况 isPalindrome[i][j] = true; start=i; end=j; } else if (s[i] == s[j] && isPalindrome[i + 1][j - 1]) { isPalindrome[i][j] = true; start=i; end=j; } } } string ret(s.begin()+start,s.begin()+end+1); return ret; } };