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:

When you see string problem that is about subsequence or matching, dynamic programming method should come to mind naturally. The key is to find the initial and changing condition.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }   
        int m = s1.length();
        int n = s2.length();

        boolean[][] res = new boolean[m+1][n+1];
        res[0][0] = true;

        for (int i = 1; i <= m; i++) {
            res[i][0] = res[i-1][0] && (s1.charAt(i-1) == s3.charAt(i-1)); 
        }

        for (int i = 1; i <= n; i++) {
            res[0][i] = res[0][i-1] && (s2.charAt(i-1) == s3.charAt(i-1)); 
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                res[i][j] = (res[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (res[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
            }
        }

        return res[m][n];
    }
}