Question

link

Given a string, convert it into a palindrome with the lease number of insertions possible.

Solution

This is a DP question. There’re 2 approaches.

First, is direct DP. This is the nicest solution, not intuitive at first, but actually good.

P[i, j] = P[i+1, j-1], if S[i] = S[j]

P[i, j] = 1 + min(P[i,j-1], P[i+1,j]), otherwise

contributed by this guy.

Second approach is to calculate the longest palindrome subsequence, and the answer would be string length minus this value.

I wrote code for both apporaches.

According to G4G, we can actually calculate the Longest Common Subsequence of the string and its reverse, and this value shall be same as the longest palindrome subsequence that we got in second approach. It’s nice to know this idea.

Code

direct

public int solve1(String str) {
    // direct dp
    if (str == null)
        return 0;
    int len = str.length();
    int[][] dp = new int[len][len];
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i; j < len; j++) {
            if (i == j) {
                dp[i][j] = 0;
            } else if (i + 1 == j) {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 0 : 1;
            } else {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? dp[i + 1][j - 1]
                        : 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][len - 1];
}

longest palindrome subsequence

public int solve2(String str) {
    // longest palindrome subsequence
    if (str == null)
        return 0;
    int len = str.length();
    int[][] dp = new int[len][len];
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i; j < len; j++) {
            if (i == j) {
                dp[i][j] = 1;
            } else if (i + 1 == j) {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 2 : 1;
            } else {
                dp[i][j] = str.charAt(i) == str.charAt(j) ? 2 + dp[i + 1][j - 1]
                        : Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return len - dp[0][len - 1];
}