Search code examples
pythonstringalgorithmdynamic-programminginterleave

Find the shortest interleaved string of A and B with Dynamic Programming

I'm having a problem with a question on dynamic programming.

Given two strings A and B find the shortest interleaved string of the two.

For example for A = "APPLE", B = "ABSOLUTE"

The shortest answer will be "ABPPSOLUTE" Instead answer my function returns "APPABSOLUTE"

My idea to solve this problem was to interleave A[0] and B[0] continually len(A)+len(B) times But that didn't work.

Solution

  • Here's some ideas to get you started.

    The tag wiki for dynamic programming describes it as:

    Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems

    So first, try and think of a way to solve the problem recursively. Ask: "How can I bite off a small piece of this problem and process it, in such a way that what I have left over is another example of the problem"?

    In this case, the "small piece" would be a single character, and the left over would be the remaining characters in the string. Think of the problem as "what's the shortest interleaving of the characters of these two strings, starting at position X of string A and position Y of string B"? When you call it initially, X and Y are 0.

    Three possible answers to that question are:

    • If X is not at the end of A, take the character A[X] off string A, then solve the problem recursively for for X+1,Y (find the shortest interleaving of the two strings starting at X+1,Y)
    • As above but taking a character off string B instead of A and solving recursively for X,Y+1
    • In the case that the characters of A[X] and B[Y] are identical, take the character off both and find the solution for X+1,Y+1

    If X and Y have reached the end of A and B, return an empty string.

    Return the shortest string of the above 3, added to the character from either A or B (or both) that you took off.

    When the function returns from the top level you should have your answer.

    That's the "recursive" part. The "overlapping subproblems" is about how you reuse stuff you have already calculated. In this case you can make a 2 dimensional array of strings that represents the problem solved for all the possible values of X and Y, and when entering the function, check whether you already have the answer and just return it if you do. If not then work it out as above and before returning from the function, save the value you are going to return in the array at location [X][Y].