Leetcode–Interleaving String

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:

  1. 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.
  2. 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”.
  3. Watch out for details:
    1. 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
    2. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s