Friday, December 19, 2014

Interleaving String

Given s1s2s3, 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.
Two Dimensional DP.
First, if the length of s3 doesn't equal the sum of the lengths of s1 and s2, return false.
I also checked the situation where s1 or s2 is empty.

Consider any substrings of s1.substring(0, i), s2.substring(0, j) and s3.substring(0, i + j).
If s3.charAt(i + j - 1) == s1.charAt(i), then s3.substring(0, i + j - 1) should be an interleaving of s1.substring(0, i - 1) and s2.substring(0, j). Similarly, if s3.charAt(i + j - 1) == s2.charAt(j), then s3.substring(0, i + j - 1) should be an interleaving of s1.substring(0, i) and s2.substring(0, j - 1).


public class InterLeave {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s1.length() == 0)
            return s3.equals(s2);
        if (s2 == null || s2.length() == 0)
            return s3.equals(s1);
        if (s1.length() + s2.length() != s3.length())
            return false;
        boolean[][] interleave = new boolean[s1.length() + 1][s2.length() + 1];
        interleave[0][0] = true;
        for (int i = 1; i <= s1.length(); i++)
        {
            if (s3.charAt(i - 1) == s1.charAt(i - 1) && interleave[i - 1][0])
                interleave[i][0] = true;
        }
        for (int j = 1; j <= s2.length(); j++)
        {
            if (s3.charAt(j - 1) == s2.charAt(j - 1) && interleave[0][j - 1])
                interleave[0][j] = true;
        }
        for (int i = 1; i <= s1.length(); i++)
        {
            for (int j = 1; j <= s2.length(); j++)
            {
                if(s3.charAt(i + j - 1) == s1.charAt(i - 1) && interleave[i - 1][j] 
                || s3.charAt(i + j - 1) == s2.charAt(j - 1) && interleave[i][j - 1])
                    interleave[i][j] = true;
            }
        }
        return interleave[s1.length()][s2.length()];
        
    }
}

No comments:

Post a Comment