# Backtracking and memoization: O(2^N) worst case runtime

• This problem seems to be very tricky, but in fact we can solve it with a pretty usual backtracking algorithm. There are two easy cases to consider and one complicated case:

1. Case 1: s1[i] is equal to the current character in s3, so we just move i and pos of s3 forward by one.
2. Case 2: s2[j] is equal to the current character in s3. Do the same as above, but with j
3. Case 3: s1[i] and s2[j] are equal to the current character in s3. At this point, we do not know which pointer will be the correct one to move. We just try to move pointer i and see what happens. If we are lucky, we will get a valid result. Otherwise we backtrack to this position and move pointer j forward by one.

The above algorithm takes O(2^N) runtime worst case. We can improve this by using memoization. We create a hashmap which stores indexes of the pointers to positions of s3. Whenever we find a constellation that is invalid, we store it in this map.

``````public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null || s3.length() != s1.length() + s2.length()) {
return false;
}

Map<Integer, List<Integer>> memo = new HashMap<>();
return interleave(s1, s2, s3, 0, 0, 0, memo);
}

private boolean interleave(String s1, String s2, String s3, int pos, int i, int j, Map<Integer, List<Integer>> memo) {
if (pos == s3.length()) {
return true;
} else if (memo.containsKey(pos)) {
List<Integer> indexes = memo.get(pos);
if (indexes.get(0) == i && indexes.get(1) == j) {
return false;
}
}

char s3Char = s3.charAt(pos);
boolean interleaves = false;

if (i < s1.length() && s1.charAt(i) == s3Char) {
interleaves |= interleave(s1, s2, s3, pos + 1, i + 1, j, memo);
}

if (interleaves) {
return true;
}

if (j < s2.length() && s2.charAt(j) == s3Char) {
interleaves |= interleave(s1, s2, s3, pos + 1, i, j + 1, memo);
}

if (!interleaves) {
List<Integer> indexes = new ArrayList<>();