97. Interleaving String.md

97. Interleaving String

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];
    }
}

Second Time

• Method 1: dp

  class Solution {
      public boolean isInterleave(String s1, String s2, String s3) {
          char[] s1Arr = s1.toCharArray();
          char[] s2Arr = s2.toCharArray();
          char[] s3Arr = s3.toCharArray();
          if(s1Arr.length + s2Arr.length != s3Arr.length) return false;
          boolean[][] dp = new boolean[s1Arr.length + 1][s2Arr.length + 1];
          dp[0][0] = true;
          for(int i = 1; i <= s1Arr.length; i++)
              dp[i][0] = dp[i - 1][0] && s1Arr[i - 1] == s3Arr[i - 1];
          for(int i = 1; i <= s2Arr.length; i++)
              dp[0][i] = dp[0][i - 1] && s2Arr[i - 1] == s3Arr[i - 1];
          for(int i = 1; i <= s1Arr.length; i++){
              for(int j = 1; j <= s2Arr.length; j++){
                  if(s1Arr[i - 1] == s3Arr[i + j - 1]){
                      dp[i][j] = dp[i - 1][j];
                  }
                  if(s2Arr[j - 1] == s3Arr[i + j - 1]){
                      dp[i][j] |= dp[i][j - 1];
                  }
              }
          }
          return dp[s1Arr.length][s2Arr.length];
      }
  }

Third time

• Method 1: dp

   class Solution {
   	public boolean isInterleave(String s1, String s2, String s3) {
   		char[] arr1 = s1.toCharArray();
   		char[] arr2 = s2.toCharArray();
   		char[] arr3 = s3.toCharArray();
   		if(arr1.length + arr2.length != arr3.length) return false;
   		boolean[][] dp = new boolean[arr1.length + 1][arr2.length + 1];
   		dp[0][0] = true;
   		for(int i = 0; i < arr1.length; i++){
   			if(arr1[i] == arr3[i])
   				dp[i + 1][0] = dp[i][0];
   		}
   		for(int i = 0; i < arr2.length; i++){
   			if(arr2[i] == arr3[i])
   				dp[0][i + 1] = dp[0][i];
   		}
   		for(int i = 1; i <= arr1.length; i++){
   			for(int j = 1; j <= arr2.length; j++){
   				// dp[i][j] saves if i + j - 1 can be constructed by i && j
   				if(arr3[i + j - 1] == arr1[i - 1]){
   					dp[i][j] = dp[i - 1][j];
   				}
   				if(arr3[i + j - 1] == arr2[j - 1]){
   					dp[i][j] |= dp[i][j - 1];
   				}
   			}
   		}
   		return dp[arr1.length][arr2.length];
   	}
   }