Interleaving String (Java)

	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 DP
	public class Solution {
	public boolean isInterleave(String s1, String s2, String s3) {
	if(s1==null||s2==null||s3==null){
	return false;
	}
	if (s1.length()+s2.length()!=s3.length()){
	return false;
	}
	boolean[][] checker=new boolean[s1.length()+1][s2.length()+1];
	checker[0][0]=true;
	for (int i=1; i<=s2.length(); i++){
	if (s2.charAt(i-1)==s3.charAt(i-1)){
	checker[0][i]=true;
	}
	}
	for (int i=1; i<=s1.length(); i++){
	if (s1.charAt(i-1)==s3.charAt(i-1)){
	checker[i][0]=true;
	}
	}
	for (int i=1; i<=s1.length(); i++){
	char c1=s1.charAt(i-1);
	for (int j=1; j<=s2.length(); j++){
	char c2=s2.charAt(j-1);
	char c3=s3.charAt(i+j-1);
	if (c3==c1){
	checker[i][j]=checker[i-1][j];
	}
	if (c3==c2){
	checker[i][j]=checker[i][j]||checker[i][j-1];
	}
	}
	}
	return checker[s1.length()][s2.length()];
	}
	}

view raw Interleaving String.java hosted with ❤ by GitHub