Find if a string is interleaved of two other strings

 Find if a string is interleaved of two other strings

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	bool isInterleaved(string a, string b, string c)
	{
	int m = a.length();
	int n = b.length();
	bool dp[m + 1][n + 1];
	memset(dp, 0, sizeof dp);
	if ((m + n) != (int)c.length()) return false;
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0 && j == 0) dp[i][j] = true; // two string empty
	else if (i == 0 && b[j - 1] == c[j - 1]) //a empty
	dp[i][j] = dp[i][j - 1];
	else if (j == 0 && a[i - 1] == c[i - 1]) // b empty
	dp[i][j] = dp[i - 1][j];
	else if (a[i - 1] == c[i + j - 1] && b[j - 1] != c[i + j - 1]) // c match only with a
	dp[i][j] = dp[i - 1][j];
	else if (a[i - 1] != c[i + j - 1] && b[j - 1] == c[i + j - 1]) // only b
	dp[i][j] = dp[i][j - 1];
	else if (a[i - 1] == c[i + j - 1] && b[j - 1] == c[i + j - 1]) // both
	dp[i][j] = (dp[i - 1][j] || dp[i][j - 1]);
	}
	}
	return dp[m][n];
	}
	void solve(char *A, char *B, char *C)
	{
	if (isInterleaved(A, B, C))
	cout << C << " is interleaved of " << A << " and " << B << endl;
	else
	cout << C << " is not interleaved of " << A << " and " << B << endl;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	solve("XXY", "XXZ", "XXZXXXY");
	solve("XY" , "WZ" , "WZXY");
	solve ("XY", "X", "XXY");
	solve ("YX", "X", "XXY");
	solve ("XXY", "XXZ", "XXXXZY");
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Guitar Strings.cpp hosted with ❤ by GitHub

Share: