Dynamic programming: transformation of one string into another

Question

We have two strings a and b. We need to transform string a into b.

Transformation rule

1. Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in a.

eg.

a = daBcd 
b = ABC

Capitalize a and c and remove d from string a. So we can transform a into b. (I found this problem on HackerRank)

So I wrote java code as below:

static boolean abbreviation(String a, String b, int i, int j, Map<String, Boolean> memo) {
        if(j==b.length()){
            if(i==a.length())
                return true;

            return !a.substring(i, a.length()).matches("\\D*[A-Z]+\\D*");
        }

        if(i==a.length())
            return false;



        String key = i+"-"+j;

        if(memo.containsKey(key))
            return memo.get(key);


        if(a.substring(i).equalsIgnoreCase(b.substring(j))){
            memo.put(key, true);
            return true;
        }


        if(Character.isUpperCase(a.charAt(i))){
            if(a.charAt(i)==b.charAt(j)){
                memo.put(key, abbreviation(a, b, i+1, j+1, memo));
                return memo.get(key);
            }
            else{
                memo.put(key, false); 
                return false;
            }
        }


        if(abbreviation(a, b, i+1, j, memo)){
            memo.put(key, true);
            return true;
        }
        else if(Character.toUpperCase(a.charAt(i))==b.charAt(j)){
            memo.put(key, abbreviation(a, b, i+1, j+1, memo));
            return memo.get(key);
        }
        else{
            memo.put(key, false);
            return false;
        }
    }

It is working fine but giving timeout for large test cases. I used hashmap for memoization but still it was giving timeout. So I looked into the editor solution, it is something like this:

static boolean abbreviationOptimal(String a, String b){
        char[] s = a.toCharArray();
        char[] t = b.toCharArray();
        int n = s.length;
        int m = t.length;

        //created memoization table for dynamic programming
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;

        //Cannot understand logic behind this--
        for(int i = 0;i <= n;i++){
            for(int j = 0;j <= m;j++){
                //what are these conditions here (all three if)
                if(i < n && s[i] >= 'a' && s[i] <= 'z'){
                    //why |= operator here
                    dp[i+1][j] |= dp[i][j];
                }
                if(i < n && j < m && s[i] == t[j]){
                    dp[i+1][j+1] |= dp[i][j];
                }
                if(i < n && j < m && s[i]+'A'-'a' == t[j]){
                    dp[i+1][j+1] |= dp[i][j];
                }
            }
        }

        return dp[n][m];
    }

I have no idea, what is happening in this function. Required some clear explanation on this.

Answer 1

In the solution dp has boolean value which indicates if it's possible to reach to position where i characters have been matched from a and j characters from b. If we have reached state dp[i][j] then we can:

• Delete ith character from a if it is lowercase in order to reach dp[i + 1][j]
• Match ith character from a with jth character from b in order to reach dp[i + 1][j + 1]

If we can reach state dp[a.length()][b.length()] then transformation can be done. Here's a bit shorter example with couple of comments, hope it helps:

static String abbreviation(String a, String b) {
    // Complete this function
    char[] x = a.toCharArray();
    char[] y = b.toCharArray();
    boolean[][] dp = new boolean[x.length + 1][y.length + 1];

    // 0 consumed from a, 0 consumed from b is reachable position
    dp[0][0] = true;

    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j <= y.length; j++) {
            // Delete lowercase char from a
            if (Character.isLowerCase(x[i])) {
                dp[i + 1][j] |= dp[i][j];
            }

            // Match characters, make sure char from a is upper case
            if (j < y.length && Character.toUpperCase(x[i]) == y[j]) {
                dp[i + 1][j + 1] |= dp[i][j];
            }
        }
    }

    return dp[x.length][y.length] ? "YES" : "NO";
}