2014年2月18日星期二

LeetCode - 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) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s1==null || s2==null || s3==null || s1.length()+s2.length()!=s3.length()) {
            return false;
        }
        boolean match[][] = new boolean[s1.length()+1][s2.length()+1];
        match[0][0] = true;
        for(int i=1;i<=s1.length();i++) {
            match[i][0] = match[i-1][0] && (s1.charAt(i-1)==s3.charAt(i-1));
        }
        for(int i=1;i<=s2.length();i++) {
            match[0][i] = match[0][i-1] && (s2.charAt(i-1)==s3.charAt(i-1));
        }
        for(int i=0;i<s1.length();i++) {
            for(int j=0;j<s2.length();j++) {
                match[i+1][j+1] = (s3.charAt(i+j+1)==s1.charAt(i) && match[i][j+1]) ||
                                    (s3.charAt(i+j+1)==s2.charAt(j) && match[i+1][j]);
            }
        }
        return match[s1.length()][s2.length()];
    }
}

没有评论:

发表评论