Interweaving Strings

• Time : O(nm)
• Space : O(nm)

using namespace std;

bool interweavingStrings(string one, string two, string three) {
  int len1 = one.length(), len2 = two.length(), len3 = three.length();
	if(len1 + len2 != len3) return false;
	
	vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1));
	dp[0][0] = true;
	for(int i = 0; i <= len1; i++) {
		for(int j = 0; j <= len2; j++) {
			if(!dp[i][j]) continue;

			int l3 = i + j;
			if(i < len1 and three[l3] == one[i])
				dp[i+1][j] = true;
			if(j < len2 and three[l3] == two[j])
				dp[i][j+1] = true;
		}
	}
	
  return dp[len1][len2];
}