Interleaving Strings


  • 1

    Click here to see the full article post


  • 1
    C

    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


  • 0

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


  • 0

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


  • 0
    S

    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)


  • 0
    C

    @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.


  • 0
    M

    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.


  • 0
    I

    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/


  • 0
    R

    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;
    }
    

    }


Log in to reply
 

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