Strings and dynamic programming algorithm

Question

A string Z is a merge of two other strings X and Y if Z is a concatenation of substrings of X and Y , in order. For example “strMERingGE” is a merge of “string” and “MERGE”. Give a dynamic programming algorithm that takes 3 strings and tests if the third is a merge of the first two.

This problem looks like a variation of the longest common subsequence problem, I tried this algorithm but I an not sure about it.

public static String concat(String s1, String s2) {
if (string.IsNullOrEmpty(s1))
    return s2;
if (string.IsNullOrEmpty(s2) )
    return s1;



int len1 = s1.Length - 1;
char last1 = s1[len1];
char first2 = s2[0];


    if (s1[len1 - indexOfLast2] == first2)
    {

int inLast2 = s2.LastIn(last1, Math.Min(len1, s2.Length - 1));
while (inLast2 != -1)
{
        int x = inLast2;
        while ((x != -1) && (s1[len1 - inLast2 + x] == s2[x]))
            x--;
        if (x == -1)
            return s1 + s2.Substring(Last2 + 1);
    }
inLast2 = s2.LastIn(last1, inLast2 - 1);

}


if ( s1 + s2.Substring(Last2 + 1) == 2)
return inLast2  +1;

An almost identical version of this question was the last problem on my Algorithms exam yesterday. You're almost on the right track, but dynamic programming implies some sort of recursion call using arrays. Also, this algorithm would be more of a boolean return value than a String. — Jason
– Jason, Commented Feb 17, 2012 at 23:44

ElKamina · Accepted Answer · 2012-02-18 00:09:41Z

3

Use this dynamic programming recursion:

Match(i,j) = Match(i-1,j) AND (Z[i+j] == X[i]) OR Match(i,j-1) AND (Z[i+j] == Y[j])

This will give a 2D binary matrix. If there is a path (continuous True, only up or left, not across) between end and beginning, there is a solution (Solution given by translating up to X and left to Y matchings).

PS:Use the following function and the matrix will automatically remember the path:

Match(i,j) = 
    if Match(i-1,j) AND (Z[i+j] == X[i]):
        1
    elif Match(i,j-1) AND (Z[i+j] == Y[j]):
        2
    else:
        0

edited Feb 18, 2012 at 0:09

answered Feb 17, 2012 at 23:58

ElKamina

7,82730 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lara Over a year ago

Thanks dear ElKamina. I am just wondering if should I this finction after I have determine the index of both S1 and S2 as I wrote in the algorithm above ?

Igor ostrovsky Over a year ago

This is the correct answer. @Lara: You'll call Match(X.Length-1, Y.Length-1), which gives you the answer. You have to add memoization to the recursive function, or rewrite it in a way that iteratively fills out a table.

ElKamina Over a year ago

@Lara As Igor mentioned just memorize values of Match(i,j), and call Match(length(X)-1,length(Y)-1)

Diego · Accepted Answer · 2012-02-17 23:39:45Z

0

It sounds to me more similar to the edit distance algorithm than longest common subsequence.

If lengths of X and Y are m and n, create a (m+1)-by-(n+1) matrix. Starting at cell (i, j)=(0,0), traverse Z, and move one cell right (j+1) in the matrix if the current character equals X[j], and one down (i+1) if the current character equals Y[i]. Output true if you end up at cell (m+1,n+1), and false if you can't match a character in either string at any point or you end up in some other cell.

For the edit distance algorithm, which is very similar, see: http://en.wikipedia.org/wiki/Levenshtein_distance

answered Feb 17, 2012 at 23:39

Diego

18.5k5 gold badges67 silver badges68 bronze badges

Comments

Jean-Pascal Billaud · Accepted Answer · 2012-02-19 05:06:29Z

-1

I have not gone through your stuff but indeed I feel this could be solved with a LCS algorithm. Really what you need to find out is:

Is LCS(Z,Y) == Y
Is LCS(Z,X) == X
Is Sorted(X+Y) == Sorted(Z)

Intuitively that seems to do the trick...

edited Feb 19, 2012 at 5:06

answered Feb 17, 2012 at 23:36

Jean-Pascal Billaud

3033 silver badges11 bronze badges

1 Comment

Jean-Pascal Billaud Over a year ago

Good point... I will be careful with my intuition next time :)

Collectives™ on Stack Overflow

Strings and dynamic programming algorithm

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related