Thursday, March 21, 2013

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.


Two dimentional dynamic programming
map[i][j] = true if s1[0,i-1] and s2[0,j-1] interleaves into s3[0,i+j-1].

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s3.length() != s1.length() + s2.length())
            return false;
       
        boolean[][] mat = new boolean[s1.length() +1][s2.length()+1];
        for(int i = 0; i < mat.length; i++){
            for(int j = 0; j < mat[i].length; j++)
                mat[i][j] = false;
        }
        mat[0][0] = true;
       
        for(int i = 1; i <= s1.length(); i++){
            if(s1.charAt(i-1) == s3.charAt(i-1)){
                mat[i][0] = true;
            }
            else break;
        }
       
        for(int i = 1; i <= s2.length(); i++){
            if(s2.charAt(i-1) == s3.charAt(i-1)){
                mat[0][i] = true;
            }
            else break;
        }
       
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                char c1 = s1.charAt(i-1);
                char c2 = s2.charAt(j-1);
                char c3 = s3.charAt(i+j-1);
                if(c1 == c3) mat[i][j] |= mat[i-1][j];
                if(c2 == c3) mat[i][j] |= mat[i][j-1];
            }
        }
        return mat[s1.length()][s2.length()];
       
    }
}

No comments:

Post a Comment

Manacher's Longest Palindromic Substring Algorithm

http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/