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.

最简单思路就是递归去做，可是这样须要递归最多s3长度的层次。消耗比較大，非常easy出现超时错误。进行递归尝试果然出现超时错误，可是递归是解决问题最直观的方法。

递归方法不行考虑DP，我们用path[i][j] 记录s1到i 和s2到j 和s3[i+j-1]是否满足要求，这个过程就是填一张二维数组表的过程，先初始化第一行和第一列。然后填表计算出全部。返回path[s1.length][s2.length]的值。

已经AC的代码：

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

}