记录
23:29 2024-2-5
https://leetcode.cn/problems/longest-palindromic-substring/
dp[i][j] s[i, j] 之间能否构成回文子串
[i,j]之间是否能够构成需要考虑[i+1, j-1]是否构成回文子串且s[i] == s[j]
当j-1 >= i+1 时候说明正好是 俩个相邻的字符，此时如果s[i] == s[j]就肯定可以构成回文子串
点击查看代码
class Solution {
public:
// dp[i][j] [i, j] 之间能否构成回文子串
/* dp[i][j] = {
dp[i + 1][j - 1] if j - 1 >= i + 1 && s[i] == s[j]
1 else s[i] == s[j]
}*/
string longestPalindrome(string s) {
int dp[s.size()][s.size()];
memset(dp, 0, sizeof(dp));
int begin = 0, maxSize = 1;
for(int i = s.size() - 1; i >= 0; i--) dp[i][i] |= 1;
for(int i = s.size() - 1; i >= 0; i--) {
for(int j = i + 1; j < s.size(); j++) {
if(s[i] == s[j]) {
if(j-1 >= i+1) {
dp[i][j] |= dp[i+1][j-1];
} else {
dp[i][j] |= 1;
}
//注意需要判断dp[i][j]
if(dp[i][j] && maxSize < j - i + 1) {
maxSize = j - i + 1;
begin = i;
}
}
}
}
return s.substr(begin, maxSize);
}
};