Longest Palindromic Substring
Given a string S,find the longest palindromic substring in S. You may assume that the maximum length of S is 1000,and there exists one unique longest palindromic substring.
题意：求原串中最长的回文子串
思路：DP做法就是：还是判断两边，往中间缩，O(n^2)的做法
class Solution {
public:
string longestPalindrome(string s) {
if (s.length() == 0) return "";
int len = s.length();
int f[len][len];
memset(f,sizeof(f));
int ans = 1;
int start = 0;
for (int i = 0; i < len; i++) {
f[i][i] = 1;
for (int j = 0; j < i; j++) {
if (s[j] == s[i] && (i - j < 2 || f[j+1][i⑴]))
f[j][i] = 1;
if (f[j][i] && i - j + 1 > ans){
ans = i - j + 1;
start = j;
}
}
}
return s.substr(start,ans);
}
};
