LeetCode Q97: Interleaving String (hard)

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. 

Question should be solved using DP.

Idea is to consider whether  the first (i+j) substring of s3 is a interleaving of s1(0:i) and s2(0:j).

To decide (i, j) entry of a tracking table, we should look at two entries (i-1, j) and (i, j-1). Because, if (i, j) is an interleaving of s1(0:i) and s2(0:j). Then it must be one of following two cases:

Case 1. if Table(i-1, j) is an interleaving. Then Table(i, j) is an interleaving too when s1(i-1) == s3(i+j-1). Because the character s(i-1) must be added to the tail of s3(0:i+j-2) to become to s2(0:i+j-1) .

Case 2. if Table(i, j-1) is an interleaving. Then Table (i, j) is an interleaving too when s2(j-1) == s3(i+j-1). The reason is as similar as Case 1.

So, Table(i, j) will be true when any of above cases is true. Otherwise Table(i, j) is a false.

	class Solution {
	public:
	bool isInterleave(string s1, string s2, string s3) {
	vector<vector<bool> > myMap(s1.length()+1, vector<bool> (s2.length()+1, false));
	if(s1.length()+s2.length()!=s3.length())
	return false;
	for(int i=0; i<=s2.length(); i++){
	if(i==0)
	myMap[0][i]=true;
	else{
	myMap[0][i]=myMap[0][i-1]&&s2[i-1]==s3[i-1];
	}
	}
	for(int i=0; i<=s1.length(); i++){
	if(i==0)
	myMap[i][0]=true;
	else{
	myMap[i][0]=myMap[i-1][0]&&s1[i-1]==s3[i-1];
	}
	}
	for(int i=1; i<=s1.length(); i++){
	for(int j=1; j<=s2.length(); j++){
	myMap[i][j]=(myMap[i-1][j]&&s1[i-1]==s3[i+j-1])||(myMap[i][j-1]&&s2[j-1]==s3[i+j-1]);
	}
	}
	return myMap[s1.length()][s2.length()];
	}
	};

view raw Q97InterleavingString.cpp hosted with ❤ by GitHub