Question

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Thinking:

  • Method 1:dp, this is the first time that I solved a dp hard question without any hint.
    • how to create the dp array: dp[i][j], where i mean s1 provides the ith character, j means s2 provides the jth character, currently, length of created string is i + j - 1;
    • initialization:
      • dp[0][0] = true.
      • for i == 0, means the string is fully constructed by s2, dp[0][j] = dp[0][j - 1] && (s2.charAt(j - 1) == s3.charAt(j - 1)), same thing in j = 0. Or we can just use startsWith to check.
      • for dp[i][j]: either one works is fine.
        • dp[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1))
        • dp[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1)) 
          class Solution {
  public boolean isInterleave(String s1, String s2, String s3) {
  if(s1 == null || s2 == null || s3 == null) return false;
  int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
  if(len1 + len2 != len3) return false;
  boolean[][] dp = new boolean[len1 + 1][len2 + 1];
  char[] s3Char = s3.toCharArray();
  dp[0][0] = true;
  for(int i = 1; i <= len1; i++){
 dp[i][0] = dp[i - 1][0] && (s3Char[i - 1] == s1.charAt(i - 1));
  }
  for(int i = 1; i <= len2; i++){
 dp[0][i] = dp[0][i - 1] && (s3Char[i - 1] == s2.charAt(i - 1));
  }
  for(int i = 1; i <= len1; i++){
 for(int j = 1; j <= len2; j++){
  dp[i][j] = (dp[i][j - 1] && (s3Char[i + j - 1] == s2.charAt(j - 1)))
      || (dp[i - 1][j] && (s3Char[i + j - 1] == s1.charAt(i - 1)));
 }
  }
  return dp[len1][len2];
  }
}