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:

- Case 1:
*s1[i]*is equal to the current character in*s3*, so we just move*i*and*pos*of*s3*forward by one. - Case 2:
*s2[j]*is equal to the current character in*s3*. Do the same as above, but with*j* - 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<>();
indexes.add(i);
indexes.add(j);
memo.put(pos, indexes);
}
return interleaves;
}
```