String Interleave

#include<iostream>
#include<cstring>
using namespace std;

class interleaved {
	public:
		void getText(string fst, string snd, string txt) {
			if (isInterleaved(fst, snd, txt))
				cout << txt <<" is interleaved of " << fst <<" and " << snd << endl;
			else
				cout << txt <<" is not interleaved of " << fst <<" and " << snd << endl;
		}

		bool isInterleaved(string sub1, string sub2, string maintxt) {

			/* Get lengths of the strings */
			int m = sub1.length();
			int n = sub2.length();

			/* 2D array store solutions of subproblems. maintxt[i][j] will be true if maintxt[0..i+j-1] is an interleaving of sub1[0..i-1] and sub2[0..j-1]. */
			bool cache[n+1][n+1];

			/* Initialize all values as false. */
			memset(cache, 0, sizeof cache);

			/* 'maintxt' can be an interleaving of 'sub1' and 'sub2' only of sum of lengths of 'sub1' & 'sub2' is equal to length of 'maintxt'. */
			if ((m+n) != maintxt.length())
				return false;
			
			for (int i = 0; i <= m; i++) {
				for (int j = 0; j <= n; j++) {

					/* Two empty strings have an empty string as interleaving */
					if (i==0 && j==0)
						cache[i][j] = true;

					/* 'sub1' is empty */
					else if (i == 0 && sub2[j-1] == maintxt[j-1])
						cache[i][j] = cache[i][j-1];

					/* 'sub2' is empty */
					else if (j == 0 && sub1[i-1] == maintxt[i-1])
						cache[i][j] = cache[i-1][j];

					/* Current character of 'maintxt' matches with current character of 'sub1', but not match with current character of 'sub2' */
					else if(sub1[i-1] == maintxt[i+j-1] && sub2[j-1] != maintxt[i+j-1])
						cache[i][j] = cache[i-1][j];

					/* Current character of 'maintxt' matches with current character of 'sub2', but not match with current character of 'sub1' */
					else if (sub1[i-1] != maintxt[i+j-1] && sub2[j-1] == maintxt[i+j-1])
						cache[i][j] = cache[i][j-1];

					/* Current character of 'maintxt' matches with both 'sub1' and 'sub2' */
					else if (sub1[i-1] == maintxt[i+j-1] && sub2[j-1] == maintxt[i+j-1])
						cache[i][j] = (cache[i-1][j] || cache[i][j-1]) ;
				}
			}
			return cache[m][n];
		}

}; 


int main() {
	interleaved inleav;
	inleav.getText("ab" ,"cd" ,"abcd");
	inleav.getText("ad" ,"cb" ,"abcd");
	inleav.getText("bc", "a", "abc");
	inleav.getText("cb", "a", "aab");
	inleav.getText("abd", "bcd", "aabcd");
	return 0;
}



/* Output */
abcd is interleaved of ab and cd
abcd is not interleaved of ad and cb
abc is interleaved of bc and a
aab is not interleaved of cb and a
aabcd is not interleaved of abd and bcd

Comments (0)

  • To add your comment please or

We use cookies to improve your experience on our site and to show you personalised advertising. Please read our cookie policy and privacy policy.

Got It!