动态规划：将一个字符串转换为另一个字符串

Question

我们有两个字符串 a 和 b。我们需要将字符串 a 转换为 b。

变换规则

1. 在某个索引 i 处将 a 的零个或多个小写字母大写（即，将它们设为大写）。
2. 删除 a 中所有剩余的小写字母。

例如。

a = daBcd 
b = ABC

a将and首字母大写，并从 中c删除。这样我们就可以转变成. （我在HackerRank上发现了这个问题）dstring aab

所以我写了如下java代码：

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;
        }
    }

它工作正常，但对于大型测试用例会超时。我使用哈希图进行记忆，但仍然超时。所以我查看了编辑器解决方案，它是这样的：

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];
    }

我不知道这个函数中发生了什么。需要对此进行一些明确的解释。

Answer 1

在解决方案中dp有布尔值，指示是否可以到达i字符已匹配的位置 froma和j字符b。如果我们已经达到状态dp[i][j]那么我们可以：

• 如果第 i 个字符是小写，则删除a它以达到dp[i + 1][j]
• 匹配第 i 个字符 froma和第 j 个字符 fromb以达到dp[i + 1][j + 1]

如果我们能够达到状态，dp[a.length()][b.length()]那么转变就可以完成。这是一个简短的示例，带有一些注释，希望对您有所帮助：

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";
}