55 lines
1.4 KiB
C++
55 lines
1.4 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
int main(){
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
int T;
|
|
if(!(cin >> T)) return 0;
|
|
while(T--){
|
|
string s;
|
|
cin >> s;
|
|
int n = s.size();
|
|
if(n == 0){
|
|
cout << 0 << "\n";
|
|
continue;
|
|
}
|
|
// isPal[i][j] whether s[i..j] is palindrome
|
|
vector<vector<char>> isPal(n, vector<char>(n, 0));
|
|
// center expand to fill isPal (or use DP)
|
|
for(int center = 0; center < n; ++center){
|
|
// odd length
|
|
int l = center, r = center;
|
|
while(l >= 0 && r < n && s[l] == s[r]){
|
|
isPal[l][r] = 1;
|
|
--l; ++r;
|
|
}
|
|
// even length
|
|
l = center; r = center + 1;
|
|
while(l >= 0 && r < n && s[l] == s[r]){
|
|
isPal[l][r] = 1;
|
|
--l; ++r;
|
|
}
|
|
}
|
|
|
|
// dp[i] = min cuts for s[0..i]
|
|
const int INF = 1e9;
|
|
vector<int> dp(n, INF);
|
|
for(int i = 0; i < n; ++i){
|
|
if(isPal[0][i]){
|
|
dp[i] = 0;
|
|
} else {
|
|
for(int j = 0; j < i; ++j){
|
|
if(isPal[j+1][i]){
|
|
dp[i] = min(dp[i], dp[j] + 1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
cout << dp[n-1] << "\n";
|
|
}
|
|
return 0;
|
|
}
|
|
|