Given three strings A, B and C. Determine if C can be created by merging A and B in a way that maintains the relative order of the characters in A and B.

Assumptions

• none of A, B, C is null

Examples

• C = "abcde", A = "acd", B = "be", return true
• C = "abcde", A = "adc", B = "be", return false

Solution: 比较a[i]与c[i + j]，b[j]与c[i + j]，所以有2种情况

dp[0][0] = true

  public boolean canMerge(String a, String b, String c) {
    if (c.length() != a.length() + b.length()) {
      return false;
    }
    boolean[][] match = new boolean[a.length() + 1][b.length() + 1];
    for (int i = 0; i < match.length; i++) {
      for (int j = 0; j < match[0].length; j++) {
        if (i == 0 && j == 0) {
          match[i][j] = true;
        }
        if (i > 0 && a.charAt(i - 1) == c.charAt(i + j - 1)) {
          match[i][j] |= match[i - 1][j];  
        }
        if (j > 0 && b.charAt(j - 1) == c.charAt(i + j - 1)) {
          match[i][j] |= match[i][j - 1]; //不能写成=，因为有2种情况
        }
      }
    }
    return match[a.length()][b.length()];
  }

或者可以写成：

    for (int i = 1; i < matrix[0].length; i++){
        matrix[0][i] = matrix[0][i-1]&&(s1.charAt(i-1)==s3.charAt(i-1));
    }

    for (int i = 1; i < matrix.length; i++){
        matrix[i][0] = matrix[i-1][0]&&(s2.charAt(i-1)==s3.charAt(i-1));
    }

    for (int i = 1; i < matrix.length; i++){
        for (int j = 1; j < matrix[0].length; j++){
            matrix[i][j] = (matrix[i-1][j]&&(s2.charAt(i-1)==s3.charAt(i+j-1)))
                    || (matrix[i][j-1]&&(s1.charAt(j-1)==s3.charAt(i+j-1)));
        }
    }