# Interleaving Strings

• I think the time complexity of recursion with memo should be O(m * n) too, since each pair of (i, j) will be computed at most once

• For the recursion case is the time complexity => O(2^​(m+n)) or O(2(m+n))?

• For the recursion with Memoization why the run time is still same as normal recursion?

• Why not just merge the two strings. A pointer into each string. If the present character in the interleaved string c equals one of the strings a or b, increase the pointer to that string and to c, if not then return false. Do this for every character in c. Complexity is O(m+n)

• @sascha.brueck.86 The problem would be you don't know which pointer to increase when the two characters pointed by the two pointers are the same as the current character.

• Both the time and space complexities for "Recursion with memoization" approach should really be O (mn). No idea why the space complexity says O(m + n). Clearly a 2D array of size mn is being used for memoization.

• Pruning to recursion solution could be very fast (without memorization).
Recursion is actually DFS when the performance are almost wasted on 'wrong' searches and re-calculating searches (solved by memorization).
The worst of DFS is O(4^n) (assume m == n then O(2^(m+n)) == O(4^n)) but the best of DFS is O(n). In this question we could have good ways to prune. The same concept of pruning is also available to DP/BFS solutions, too.
For example, grouping same letters from "aaabbccc" to {3 * a, 2 * b, 3 * c} and using random search path selection like "random ? isInterleave(sub1, sub2, sub3) : isInterleave(sub2, sub1, sub3)" to avoid search trap ("abcabcabcX", "abcabcabcY", "abcabcabcYabcabcabcX").
My example is:
https://leetcode.com/submissions/detail/136427963/

• Here is my solution that got accepted with codelab.
public class Solution {
public int isInterleave(String a, String b, String c) {
return interleave(a,0,b,0,c,0);
}

``````private static int interleave(String a, int ai, String b, int bi, String c, int ci) {
if (a.length() == ai && b.length() == bi && c.length() == ci) return 1;
char s = c.charAt(ci);
if (ai < a.length() && bi < b.length() && a.charAt(ai) == s && b.charAt(bi) == s) {
return interleave(a, ai + 1, b, bi, c, ci + 1) | interleave(a, ai, b, bi + 1, c, ci + 1);
}
if (ai < a.length() && s == a.charAt(ai)) {
return interleave(a, ai+1, b, bi, c, ci+1);
}
else if (bi < b.length() && s == b.charAt(bi)) {
return interleave(a, ai, b, bi+1, c, ci+1);
}
else return 0;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.