回文部分
记录子串是否为回文:
bool f[n][n];
memset(f, false, sizeof(f));
for (int i{n - 1}; i >= 0; --i)
for (int j{i}; j < n; ++j) {
if (s[i] == s[j]) {
if (j - i <= 1)
f[i][j] = true;
else if (f[i + 1][j - 1])
f[i][j] = true;
}
}
更简洁的一种方法是: (参考力扣官方题解)
注意这里初始化为 true 了.
bool f[n][n];
memset(f, true, sizeof(f));
for (int i{n - 1}; i >= 0; --i)
for (int j{i + 1}; j < n; ++j)
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];