P206 字符串的交错合并

描述#

这个题目说的是，给你 3 个字符串 s1, s2 和 s3，你要判断 s1 和 s2 是否可以交错合并形成 s3。

比如说，给你的 s1, s2, s3 分别是：
s1 = abd
s2 = bcca
s3 = abcbcad
s3 整个字符串，是由 s1 和 s2 上的所有字符，按从左到右的顺序交错合并而成。因此，对于这个例子我们要返回 true。
如果把 s3 首尾两个字符对调一下：
s3 = dbcbcaa
那么 s3 就无法由 s1 和 s2 交错合并形成，返回 false。

代码#

public class AlgoCasts {

  // Time: O(n1*n2), Space: O(n1*n2*n3)
  public boolean isInterleave3DArray(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null) return false;
    int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
    if (n1+n2 != n3) return false;
    boolean[][][] d = new boolean[n1+1][n2+1][n3+1];
    d[0][0][0] = true;

    for (int i = 1; i <= n1; ++i)
      d[i][0][i] = d[i-1][0][i-1] && s1.charAt(i-1) == s3.charAt(i-1);
    for (int j = 1; j <= n2; ++j)
      d[0][j][j] = d[0][j-1][j-1] && s2.charAt(j-1) == s3.charAt(j-1);

    for (int i = 1; i <= n1; ++i) {
      for (int j = 1; j <= n2; ++j) {
        int k = i + j;
        d[i][j][k] = (d[i-1][j][k-1] && s1.charAt(i-1) == s3.charAt(k-1))
          || (d[i][j-1][k-1] && s2.charAt(j-1) == s3.charAt(k-1));
      }
    }
    return d[n1][n2][n3];
  }

  // Time: O(n1*n2), Space: O(n1*n2)
  public boolean isInterleave2DArray(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null) return false;
    int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
    if (n1+n2 != n3) return false;
    boolean[][] d = new boolean[n1+1][n2+1];
    d[0][0] = true;

    for (int i = 1; i <= n1; ++i)
      d[i][0] = d[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
    for (int j = 1; j <= n2; ++j)
      d[0][j] = d[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);

    for (int i = 1; i <= n1; ++i) {
      for (int j = 1; j <= n2; ++j) {
        int k = i + j;
        d[i][j] = (d[i-1][j] && s1.charAt(i-1) == s3.charAt(k-1))
          || (d[i][j-1] && s2.charAt(j-1) == s3.charAt(k-1));
      }
    }
    return d[n1][n2];
  }

}