给定一个字符串S,我们需要判断是否可以通过删除其中一项来使它成为回文。我采用了修改编辑距离方法的O(N ^ 2)方法。是否有更好的方法呢?
我的方法:
int ModifiedEditDistance(const string& a, const string& b, int k) {
int i, j, n = a.size();
int dp[MAX][MAX];
memset(dp, 0x3f, sizeof dp);
for (i = 0 ; i < n; i++)
dp[i][0] = dp[0][i] = i;
for (i = 1; i <= n; i++) {
int from = max(1, i-k), to = min(i+k, n);
for (j = from; j <= to; j++) {
if (a[i-1] == b[j-1]) // same character
dp[i][j] = dp[i-1][j-1];
// note that we don't allow letter substitutions
dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j
dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i
}
}
return dp[n][n];
}
如何改善空间复杂度,因为字符串的最大大小可以达到10^5。
请帮忙。
例子:如果字符串是abc,则答案是“NO”,如果字符串是“abbcbba”,则答案是“YES”。