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.

 

Solution:

F[i][j]代表S1的前i个字符和S2的前j个字符与S3的前i+j个字符是否interleave。

• 如果S1[i-1]==S3[i+j-1]，F[i][j] = F[i][j] || F[i-1][j]。
• 如果S2[j-1]==S3[i+j-1]，F[i][j] = F[i][j] || F[i][j-1]。

 

public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length(), l = s3.length();
    if(m+n!=l) return false; //长度不相等的话直接返回
    boolean[][] f = new boolean[m+1][n+1];
    f[0][0] = true; //s1=s2=s3=""，三者都是空字符串的时候，为true
    
    for(int i=1; i<=m && i<=l; i++) {
        f[i][0] = (s1.charAt(i-1) == s3.charAt(i-1));
        if(!f[i][0]) break; //如果这里不匹配，那么后面的都不匹配
    }
    for(int j=1; j<=n && j<=l; j++) {
        f[0][j] = (s2.charAt(j-1) == s3.charAt(j-1));
        if(!f[0][j]) break; //如果这里不匹配，那么后面的都不匹配
    }
    
    for(int i=1; i<=m; i++) {
        char c1 = s1.charAt(i-1);
        for(int j=1; j<=n; j++) {
            char c2 = s2.charAt(j-1);
            char c3 = s3.charAt(i+j-1);
            if(c1==c3) {
                f[i][j] = f[i][j] || f[i-1][j];
            }
            if(c2==c3) {
                f[i][j] = f[i][j] || f[i][j-1];
            }
        }
    }
    return f[m][n];
}