How can I convert a string to a palindrome with as few string deletions as possible?
suppose the string is "anuja", the result should be 2, because if I remove the characters "u" and "n", the given string becomes a palindrome. Thus, the output should be as few paragraphs as possible. more examples: input line: "ababa" output: 0 (no delete required) input line: "abcdba" output: 1 (delete "c" or "d") explain the algorithm.
source to share
Let dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome
. We have:
dp[i, i] = 0 for all i (every single character is a palindrome)
To find dp[i, j]
, consider a random string. We have two possibilities:
-
The first and last characters are equal
a[i] == a[j]
. In this case, we can reduce the problem to finding the minimum number of characters that need to be removed to make the substring a[i+1, j-1]
palindrome. -
The first and last characters are not equal:
a[i] != a[j]
. In this case, we need to remove one of them. We will remove whatever leads us to the best solution.
So we have:
dp[i, j] = dp[i + 1, j - 1] # if a[i] == a[j]
min(dp[i + 1, j], dp[i, j - 1]) + 1 # otherwise
An example of yours anuja
. we'll get:
| 1 2 3 4 5
-------------
1 | 0 1 2 2 2
2 | 0 1 2 3
3 | 0 1 2
4 | 0 1
5 | 0
Note that the matrix is calculated starting at the main diagonal and continuing up, in order, with diagonals parallel to the main diagonal. Answer dp[1, n]
.
This is similar to Levenshtein distance , but it only takes into account distance.
source to share
You can measure the edit distance (levenshtein distance) from a string to its back (ignoring replacements). The desired value will be half that value.
This problem is similar to UVA 10739 . Here's an example.
An example implementation (adapted to your case) could be:
string P, Q;
getline(cin, P);
Q = string(P.rbegin(), P.rend());
int p = P.size(), q = Q.size();
for(int i=0; i<=p; i++) { T[i][0] = i; }
for(int i=0; i<=q; i++) { T[0][i] = i; }
for(int i=1; i<=p; i++) {
for(int j=1; j<=q; j++) {
if (P[i-1] == Q[j-1])
T[i][j] = T[i-1][j-1];
else
T[i][j] = min(T[i-1][j], T[i][j-1]) + 1;
}
}
cout << "Case " << tt << ": " << T[p][q]/2 << endl;
source to share