Question

LCS (Longest Common Subsequence) problem consists in finding the longest subsequence of characters that is present in two given sequences in the same order.

A subsequence is a sequence of characters that don't have to be consecutive.

For example, for the following inputs, the length of the LCS is 4

X: ABCBDAB

Y: BDCABA

And one of the LCS is BDAB

The following code is a solution for such problem, which values must be stored in the variable key for it to properly work?

Inputs: X and Y are strings to be analysed. n is the number of characters in X. m is the number of characters in Y. table is a dictionary with the solutions to the subproblems.

Output: The maximum number of characters in a LCS of X and Y

function LCS(X, n, Y, m, table)

    if n < 0 or m < 0

        return 0

    if key not in table

        if X[n] == Y[m]

            table[key] = LCS(X, n-1, Y, m-1, table) + 1

        else

            in_x = LCS(X, n-1, Y, m, table)

            in_y = LCS(X, n, Y, m-1, table)

            table[key] = max(in_x, in_y)

    

    return table[key]

a) X and Y

b) n

c) m

d) m and n

e) The base cases

Which is the correct answer?

Answer 1

Option (d) is the correct answer.

The values of m and n (length of both strings) must be stored in the variable key for the proper working of the code. At first, we must check if the end for either sequence has reached. If not, then we must check if the last character of the strings matches. We also need to check the condition if they don't match.

Option (a) is incorrect as we need to store the string lengths, not the strings.

Option (b) is incorrect as both m and n must be stored.

Option (c) is incorrect as both m and n must be stored.

Option (e) is incorrect as the base case will be the not null check.

Please comment in case of any doubt.
Please upvote if this helps.