6/19/2014

132. Interleaving String

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
       
        if (l1+l2!=l3) return false;
       
        boolean[][] table = new boolean[l1+1][l2+1];
       
        for (int i=0; i<=l1; i++) {
            for (int j=0; j<=l2; j++) {
                if (i==0 && j==0) {
                    table[i][j] = true;
                } else if (i==0 && s3.charAt(j-1)==s2.charAt(j-1)) {
                    table[i][j]=table[i][j-1];
                } else if (j==0 && s3.charAt(i-1)==s1.charAt(i-1)) {
                    table[i][j]=table[i-1][j];
                }
               
                if (i!=0 && j!=0) {
                    if (s3.charAt(i+j-1)==s1.charAt(i-1) && s3.charAt(i+j-1)!=s2.charAt(j-1)) {
                        table[i][j]=table[i-1][j];
                    } else if (s3.charAt(i+j-1)==s2.charAt(j-1) && s3.charAt(i+j-1)!=s1.charAt(i-1)) {
                        table[i][j]=table[i][j-1];
                    } else if (s3.charAt(i+j-1)==s2.charAt(j-1) && s3.charAt(i+j-1)==s1.charAt(i-1)) {
                        table[i][j]=table[i][j-1] || table[i-1][j];
                    }
                }
            }
        }
       
        return table[l1][l2];
    }
}

没有评论:

发表评论