package general;

public class CheckInterleavedStrings {

	public static boolean isValidInterleavedString(String foo, String bar,
			String target) {
		if (foo == null || bar == null || target == null) {
			return false;
		}

		if (target.length() != foo.length() + bar.length()) {
			return false;
		}

		return isValidInterleavedString(foo, 0, bar, 0, target, 0);
	}

	private static boolean isValidInterleavedString(String foo, int fooIndex,
			String bar, int barIndex, String target, int targetIndex) {
		if (targetIndex == target.length()) {
			if (fooIndex != foo.length() || barIndex != bar.length()) {
				return false;
			}

			return true;
		}

		boolean valid = false;
		char targetChar = target.charAt(targetIndex);
		boolean found = fooIndex != foo.length() ? foo.charAt(fooIndex) == targetChar
				: false;
		if (found) {
			valid = isValidInterleavedString(foo, fooIndex + 1, bar, barIndex,
					target, targetIndex + 1);
		}

		if (!valid) {
			found = barIndex != bar.length() ? bar.charAt(barIndex) == targetChar
					: false;
			if (found) {
				valid = isValidInterleavedString(foo, fooIndex, bar,
						barIndex + 1, target, targetIndex + 1);
			}
		}

		return valid;
	}

	public static void main(String[] args) {
		System.out.println(isValidInterleavedString("abc", "def", "daecfb"));
	}
}

@@ -11,16 +11,703 @@
 neral;%0A%0A
+import java.util.HashSet;%0Aimport java.util.Set;%0A%0Aimport common.Pair;%0A%0A/**%0A * We are given 3 strings: str1, str2, and str3. Str3 is said to be a shuffle of%0A * str1 and str2 if it can be formed by interleaving the characters of str1 and%0A * str2 in a way that maintains the left to right ordering of the characters%0A * from each string. For example, given str1=abc and str2=def, str3=dabecf%0A * is a valid shuffle since it preserves the character ordering of the two%0A * strings. So, given these 3 strings write a function that detects whether str3%0A * is a valid shuffle of str1 and str2.%0A * %0A * http://www.ardendertat.com/2011/10/10/programming-interview-questions-6-combine-two-strings/%0A */%0A
 public c
@@ -1043,16 +1043,59 @@
 arget, 0
+,%0A%09%09%09%09new HashSet%3CPair%3CInteger, Integer%3E%3E()
 );%0A%09%7D%0A%0A%09
@@ -1227,19 +1227,151 @@
 getIndex
-) %7B
+,%0A%09%09%09Set%3CPair%3CInteger, Integer%3E%3E known) %7B%0A%09%09if (known.contains(new Pair%3CInteger, Integer%3E(fooIndex, barIndex))) %7B%0A%09%09%09return false;%0A%09%09%7D%0A
 %0A%09%09if (t
@@ -1786,24 +1786,31 @@
 getIndex + 1
+, known
 );%0A%09%09%7D%0A%0A%09%09if
@@ -2024,16 +2024,23 @@
 ndex + 1
+, known
 );%0A%09%09%09%7D%0A
@@ -2050,138 +2050,103 @@
 %0A%0A%09%09
-return valid;%0A%09%7D%0A%0A%09public static void main(String%5B%5D args
+if (!valid
 ) %7B%0A%09%09
+%09
-System.out.println(isValidInterleavedString(%22abc%22, %22def%22, %22daecfb%22))
+known.add(new Pair%3CInteger, Integer%3E(fooIndex, barIndex));%0A%09%09%7D%0A%0A%09%09return valid
 ;%0A%09%7D

Check interleaved strings.