# The Problem:

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

For example,

Given:

*s1* = `"aabcc"`

,

*s2* = `"dbbca"`

,

When *s3* = `"aadbbcbcac"`

, return true.

When *s3* = `"aadbbbaccc"`

, return false.

# Notes:

- I tried recursion first and it exceeds time limit. And for recursion, one immediate optimization is consider if DP could save some duplicate recursion branches.
- As for the recursive formulation, We dont need exact detail of which character in s1/s2 match to which character in s3. Instead we only care about if (part of) s1 and (part of) s2 interleave can match (part of) s3. one smart way is to record match[i][j] as “first i characters in s1 and first j characters in s2 can interleave to first i+j characters in s3”.
- Watch out for details:
- Here we have index of match represent the number of characters in s1/s2, aka. index+1. The reason to do it this way is to represent the situation of “using none of characters from s1/s2”, which cannot use match[0][j] if 0 is the index
- As a result of the shift mentioned above, the start/end condition of for loop, and the index in if condition, all needs to be carefully adjusted accordingly.

# Java Solution

public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(); int n2 = s2.length(); int n3 = s3.length(); if(n1==0) return s2.equals(s3); if(n2==0) return s1.equals(s3); if(n1 + n2 != n3 || !sameChar(s1+s2, s3)) return false; //match[i+1][j+1] means s1[0~i] and s2[0~j] can form s3[0~i+j] boolean[][] match = new boolean[n1+1][n2+1]; //start from 1 to avoid mismatch like s1[0]+s2[0]->s3[1] for(int i = 0; i <=n1; i++){ for(int j = 0; j <= n2; j++){ if(i==0 && j==0) match[i][j] = true; else if((i > 0 && s1.charAt(i-1)==s3.charAt(i+j-1) && match[i-1][j])|| (j>0 && s2.charAt(j-1)==s3.charAt(i+j-1) && match[i][j-1])) match[i][j] = true; else match[i][j] = false; } } return match[n1][n2]; } public boolean sameChar(String s1, String s2){ char[] ch1 = s1.toCharArray(); char[] ch2 = s2.toCharArray(); Arrays.sort(ch1); Arrays.sort(ch2); return new String(ch1).equals(new String(ch2)); } }

Advertisements