📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    After filling the dp table using the standard dynamic

    programming approach, we can reconstruct one of the Longest Common Subsequences by backtracking. Consider text1 = "ABCBDAB" and text2 = "BDCABA". The dp table is filled as follows:         ""  B   D   C   A   B   A     ""  0   0   0   0   0   0   0     A   0   0   0   0   1   1   1     B   0   1   1   1   1   2   2     C   0   1   1   2   2   2   2     B   0   1   1   2   2   3   3     D   0   1   2   2   2   3   3     A   0   1   2   2   3   3   4     B   0   1   2   2   3   4   4 Using the following Python code snippet for backtracking, what LCS string will be reconstructed? def reconstruct_lcs(text1, text2, dp):     lcs_str = []     i = len(text1)     j = len(text2)     while i > 0 and j > 0:         if text1[i - 1] == text2[j - 1]:             lcs_str.append(text1[i - 1])             i -= 1             j -= 1         elif dp[i - 1][j] > dp[i][j - 1]:             i -= 1         else:             j -= 1     return "".join(lcs_str[::-1]) # Reverse to get correct order
    A "BCBA" Correct Answer Incorrect Answer
    B "BDAB" Correct Answer Incorrect Answer
    C "ABCA" Correct Answer Incorrect Answer
    D "BDBA" Correct Answer Incorrect Answer

    Solution

    Detailed Answer and Dry Run: The reconstruct_lcs function starts from the bottom-right corner of the dp table (dp[m][n]) and moves upwards and leftwards. If text1[i-1] == text2[j-1], it means these characters form part of the LCS. We append text1[i-1] to our lcs_str and move diagonally up-left (i-1, j-1). If the characters don't match, we look at dp[i-1][j] (value from above) and dp[i][j-1] (value from left). We move to the cell that contributed the maximum value to dp[i][j]. If dp[i-1][j] > dp[i][j-1], we move up (i-1, j). Otherwise, we move left (i, j-1). Let's dry run with text1 = "ABCBDAB" (m=7) and text2 = "BDCABA" (n=6). Initial: i = 7, j = 6, lcs_str = [] 1.  i=7, j=6 (dp = 4)     text1[6] = 'B', text2[5] = 'A'. Mismatch.     dp[6][6] (value above) = 3     dp[7][5] (value left) = 4     Since dp[7][5] (4) is not greater than dp[6][6] (3), we move left. (Note: if they are equal, moving left or up is arbitrary, here else moves left).     i = 7, j = 5 2.  i=7, j=5 (dp = 4)     text1[6] = 'B', text2[4] = 'B'. Match!     Append 'B' to lcs_str. lcs_str = ['B']     Move diagonally up-left.     i = 6, j = 4 3.  i=6, j=4 (dp = 3)     text1[5] = 'A', text2[3] = 'A'. Match!     Append 'A' to lcs_str. lcs_str = ['B', 'A']     Move diagonally up-left.     i = 5, j = 3 4.  i=5, j=3 (dp = 2)     text1[4] = 'D', text2[2] = 'C'. Mismatch.     dp[4][3] (value above) = 2     dp[5][2] (value left) = 2     Since dp[4][3] (2) is not greater than dp[5][2] (2), we move left.     i = 5, j = 2 5.  i=5, j=2 (dp = 2)     text1[4] = 'D', text2[1] = 'D'. Match!     Append 'D' to lcs_str. lcs_str = ['B', 'A', 'D']     Move diagonally up-left.     i = 4, j = 1 6.  i=4, j=1 (dp = 1)     text1[3] = 'B', text2[0] = 'B'. Match!     Append 'B' to lcs_str. lcs_str = ['B', 'A', 'D', 'B']     Move diagonally up-left.     i = 3, j = 0 7.  i=3, j=0     j is now 0. The while loop condition j > 0 is false. Loop terminates. Finally, lcs_str = ['B', 'A', 'D', 'B']. We reverse it to get the correct order: ["B", "D", "A", "B"]. The reconstructed LCS is "BDAB".

    Practice Next
    More Data Structure Questions
    ask-question