动态编程：将一个字符串转换为另一个字符串

Question

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

转换规则

1. 大写零个或更多的是一些指数小写字母I（即，使他们大写）。
2. 删除a中所有剩余的小写字母。

例如，

a = daBcd 
b = ABC 

大写a和c和从string a除去d。所以我们可以将a转换成b。 （我发现这个问题上HackerRank）

所以我写了下面的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; 
     } 
    } 

它工作正常，但给人超时大测试用例。我使用hashmap进行记忆，但仍然超时。所以我看着编辑器解决方案，它是这样的：

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字符已被从a和j字符匹配从b位置。如果我们已经达到状态dp[i][j]那么我们就可以：

• 删除a第i个字符，如果是为了小写达到dp[i + 1][j]
• 从a匹配i个字符与b为了第j个角色达到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"; 
}