leetcode 5. 最长回文子串

题目如下

本题可以这么来想设有一个回文串s="112211"当我们去掉左右两边的"1"时s任然是回文串。
反过来说现有字符串 "x1221y"(x,y都是未知字符)当且仅当x == y时这个字符串是回文串。
故我们可以令i j为某一个字符串的左右两端然后有如下情况:
i > j 显然不行
i == j 显然单个字符组成的字符串是回文串
i == j - 1 显然只有s[i] == s[j]那就是回文串
j > i + 1 在满足i +1 j - 1 合法情况下判断左右两端为i + 1,j - 1的字符串是回文串且s[i] == s[j]
是回文串
所以我们可以通过构造一个二维数组然后从后往前遍历(因为这样才是从长度小的子串变成大的子串)

通过代码

class Solution {
public:string longestPalindrome(string s) {int n = s.size(),max = 1,l = 0,r = 0;string ans;vector<vector<bool>> dp(n,vector<bool>(n));for(int i = 0;i < n;i++) {dp[i][i] = true;}for(int i = n - 1;i >= 0;i--) {for(int j = n - 1;j >= 0;j--) {if(j == i + 1) {dp[i][j] = s[i] == s[j];}if(j > i + 1)dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];if(i > j)dp[i][j] = false;}}for(int i = 0;i < n;i++) {for(int j = 0;j < n;j++) {if(dp[i][j]) {if(max < j - i + 1) {l = i;r = j;max = j - i + 1;}}}}for(int i = l;i <= r;i++) {ans += s[i];}return ans;
}
};