题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
#include <iostream>
using namespace std;
#include <string>
#include <vector>
int main() {
string str;
getline(cin, str);
vector<vector<bool>> dp(str.size(), vector<bool>(str.size(), false));
int maxl = 0;
for (int i = str.size() - 1; i >= 0; i--) {
for (int j = i; j < str.size(); j++) {
if (str[i] == str[j]) {
if(j-i <= 1){
dp[i][j] = true;
}
else if(dp[i+1][j-1]){
dp[i][j] = true;
}
}
if(dp[i][j]){
maxl = max(j-i+1,maxl);
}
}
}
cout << maxl << endl;
}
也是回文子串的变种，
在动态规划寻找回文子串的过程中顺便记录长度
查看15道真题和解析