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

Key point: 把问题抽象成A，B的 combine 成的subsequence 可以组成C

_**// any combination of a, b is subsequece of c, would be the solution

// merge[i][j] meaning 1 - ith character of a and 1 - j th character of b is subsequence of c

小一号问题是： m[i - 1][ j ] and m[i][j - 1]

base case: m[0][0] = true

induction rule :

                m[i][j] |= m[i - 1][j]  when i > 0 and A[i] == C[i + j - 1]

                 m[i][j] |= m[i ][j - 1]  when j > 0 and B[j] == C[i + j - 1]

public class Solution {
  public boolean canMerge(String a, String b, String c) {
    // Write your solution here.
    if (a == null || b == null || c == null ) {
      return false;
    }

    if (a.length() + b.length() != c.length()) {
      return false;
    }

    // key point here is any combination of a, b is subsequece of c,would be the solution
    // merge[i][j] meaning 1 - ith character of a and 1 - j th character of b is subsequence of c
    boolean[][] merge = new boolean[a.length() + 1][b.length() + 1];
    for (int i = 0; i <= a.length() ; i++) {
      for (int j = 0; j <= b.length(); j++) {
        if (i == 0 && j == 0) {
          merge[i][j] = true;
        } 

        if (i > 0 && a.charAt(i - 1) == c.charAt(i + j - 1)) {
          merge[i][j] |= merge[i - 1][j];
        }

        if (j > 0 && b.charAt(j - 1) == c.charAt(i + j - 1)) {
          merge[i][j] |= merge[i][j - 1];
        }
       }
    }

    return merge[a.length()][b.length()];
  }


}