Saturday, January 10, 2015

LeetCode 97: Interleaving String

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.
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // DP problem
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        
        if (n1 + n2 != n3)
            return false;
        
        // match[i][j] represents if the first (i+j) elements of s3 can be interleaved by the first i elements of s1 and the first j
        // elements of s2
        boolean[][] match = new boolean[n1+1][n2+1];
        
        match[0][0] = true;
        
        // If s2 is null && s3 == s1
        for(int i = 1; i <= n1; i++)
        {
            if (s3.charAt(i-1) == s1.charAt(i-1))
                match[i][0] = true;
            else
                break;
        }
        
        // If s1 is null && s3 == s2
        for (int i = 1; i <= n2; i++)
        {
            if (s3.charAt(i-1) == s2.charAt(i-1))
                match[0][i] = true;
            else
                break;
        }
        
        for (int i = 1; i <= n1; i++)
        {
            char c1 = s1.charAt(i-1);
            
            for (int j = 1; j <= n2; j++)
            {
                char c2 = s2.charAt(j-1);
                char c3 = s3.charAt(i+j-1);
                
                // e.g., s1 --- "xxx$", s2 --- "###", s3 --- "@@@@@@$"
                // Here c1==c3 is true, if "xxx" and "###" can interleave "@@@@@@", s1 and s2 can also interleave s3.
                if (c1 == c3)
                    match[i][j] = match[i-1][j];

                // Note: "||" indicates if match[i][j] has already be true, it will still be true.
                if (c2 == c3)
                    match[i][j] = match[i][j] || match[i][j-1];
            }
        }
        
        return match[n1][n2];        
    }
}

No comments:

Post a Comment