1. 前言
回文串是指正读和反读都相同的字符串，例如“level”、“racecar”等。在字符串的处理中，回文串是比较重要的一种类型，因为很多问题都可以转化成求最长回文子串或者回文串的个数。
本文将要探讨的问题是：如何删除最小的子串，使给定的字符串成为回文。该问题可以转化为求出最小的需要删除的字符数。本文将介绍两种解决方法：动态规划和中心扩展法。
2. 动态规划
动态规划是求解最长回文子串问题的经典算法。其基本思想是：定义二维数组dp[i][j]表示区间[i,j]是否为回文串，如果是，则dp[i][j]=true，否则dp[i][j]=false。根据这个定义可以得到状态转移方程：
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
其中，如果s[i]==s[j]，则区间[i,j]如果是回文串，则区间[i+1,j-1]也必然是回文串，因此可以递推得到dp[i][j]=dp[i+1][j-1];如果s[i]!=s[j]，则区间[i,j]必须删除一个字符，才可能成为回文串，因此可以将问题转化为求解区间[i+1,j]和区间[i,j-1]的最小删除次数，即dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1。
2.1 举例说明
例如，对于字符串s="abca"，其dp数组的值为：
| | a | b | c | a |
|---|---|---|---|---|
| a | T | F | F | T |
| b | | T | F | F |
| c | | | T | F |
| a | | | | T |
根据状态转移方程，可以推导出dp[0][3]=1，即需要删除一个字符（"b"）才能使整个字符串成为回文串。
3. 中心扩展法
中心扩展法是另一种经典的求解回文串问题的算法。其基本思想是：枚举回文串的中心位置，然后向左右两端扩展，直到扩展不下为止。由于回文串长度可能是奇数也可能是偶数，因此需要分别枚举回文串中心为一个字符和两个字符的情况。
3.1 回文串中心为一个字符
假设字符串s的长度为n，那么中心位置一共有2n-1个，因为可能是单个字符，也可能是两个字符的中心。
对于中心位置为i的情况，可以从i向左侧和右侧分别扩展，直到不再为回文串为止。具体做法是，使用两个指针l和r，初始值分别为i和i，然后不断移动指针，直到s[l]!=s[r]或者越界。在移动指针的过程中，每次判断s[l]==s[r]，如果成立，则回文串长度加2，否则跳出循环。
3.2 回文串中心为两个字符
假设字符串s的长度为n，那么中心位置一共有2n个，因为必须是两个相邻的字符。
对于中心位置为(i,i+1)的情况，可以从i向左侧，从i+1向右侧分别扩展，直到不再为回文串为止。具体做法是，使用两个指针l和r，初始值分别为i和i+1，然后不断移动指针，直到s[l]!=s[r]或者越界。在移动指针的过程中，每次判断s[l]==s[r]，如果成立，则回文串长度加2，否则跳出循环。
3.3 完整代码
class Solution {
public:
int minDelete(string s) {
int n=s.length();
vector<vector<int>> dp(n,vector<int>(n,0));
for(int len=2;len<=n;len++) {
for(int i=0;i<=n-len;i++) {
int j=i+len-1;
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1];
else
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
}
}
return dp[0][n-1];
}
bool isPalindrome(string s) {
int n=s.length();
for(int i=0;i<n/2;i++) {
if(s[i]!=s[n-1-i])
return false;
}
return true;
}
int minDeletePalindrome(string s) {
if(isPalindrome(s))
return 0;
int n=s.length();
int ans=n-1;
for(int i=0;i<2*n-1;i++) {
int l,r;
if(i%2==0) { // 回文串中心为一个字符的情况
l=r=i/2;
while(l>=0 && r<n && s[l]==s[r]) {
l--;
r++;
}
int len=r-l-1;
if(len%2==0 && len>0) // 如果回文串长度是偶数，则需要删除len/2个字符
ans=min(ans,n-len/2);
else if(len%2==1 && len>0) // 如果回文串长度是奇数，则需要删除(len-1)/2个字符
ans=min(ans,n-(len-1)/2);
} else { // 回文串中心为两个字符的情况
l=i/2;
r=l+1;
while(l>=0 && r<n && s[l]==s[r]) {
l--;
r++;
}
int len=r-l-1;
if(len%2==0 && len>0) // 如果回文串长度是偶数，则需要删除len/2个字符
ans=min(ans,n-len/2);
else if(len%2==1 && len>0) // 如果回文串长度是奇数，则需要删除(len-1)/2个字符
ans=min(ans,n-(len-1)/2);
}
}
return ans;
}
};
4. 总结
本文介绍了两种解决最小删除次数问题的方法：动态规划和中心扩展法。动态规划需要用二维数组表示状态，并且需要计算所有状态的值，因此时间复杂度为O(n^2)。中心扩展法的时间复杂度为O(n^2)，但是常数较小，因此对于一些小的实例，中心扩展法可能更加高效。此外，中心扩展法的思想可以应用到许多其他问题中，例如求最长回文子串、回文串个数等，具有广泛的应用价值。
总的来说，最小删除次数问题是字符串处理中比较典型的问题，解决起来比较困难。本文介绍的两种方法各有优缺点，可以根据具体情况选择合适的算法进行求解。