Thursday, February 20, 2014

Leetcode: 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.

Solution:

We use dynamic programming, with the matrix isInterleaved whose element(i,j) indicates if string s3[0,...,i+j-1] can be formed by interleaving s1[0,...,i-1] and s2[0,...,j-1].
Then we can just calculate the element (i,j) by:

isInterleaved[i][j] = (isInterleaved[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (isInterleaved[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1))
This program could be reduced the space complexity just keeping the previousRow and actualRow, instead of the whole matrix, as done in the Python implementation.
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        boolean[][] isInterleaved = new boolean[s1.length()+1][s2.length()+1];
        if (s3.length() != s1.length()+s2.length())
            return false;
        for(int i=0; i<=s1.length(); i++)
        {
            for(int j=0; j<=s2.length(); j++)
            {
                if(i==0 && j==0)
                {
                    isInterleaved[0][0]=true;        
                    continue;
                }
                boolean value = j>0 ? isInterleaved[i][j-1] && s3.charAt(i+j-1) == s2.charAt(j-1) : false;
                value = i>0 ? value || isInterleaved[i-1][j] && s3.charAt(i+j-1) == s1.charAt(i-1) : value;
                isInterleaved[i][j] = value;
            }
        }
        return isInterleaved[s1.length()][s2.length()];
    }
}

No comments :

Post a Comment