Longest common subsequence length and backtracking the string

Question

Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Python 3 code:

def calculate_lcs_length(a,b):
    a_len = len(a)
    b_len = len(b)
    dp = []
    for i in range(a_len + 1):
        dp.append([0 for j in range(b_len + 1)])
    for i in range(1, a_len + 1):
        for j in range(1, b_len + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j - 1])
    max_length = dp[a_len][b_len]
    return dp, max_length

def get_path(a, b, dp, i, j):
    if i == 0 or j == 0:
        return ""
    if a[i-1] == b[j-1]:
        return get_path(a, b, dp, i-1, j-1) + a[i-1]
    else:
        if dp[i-1][j] > dp[i][j-1]:
            return get_path(a, b, dp, i-1, j)
        else:
            return get_path(a, b, dp, i, j-1)

if __name__ == "__main__":
    a = "ABCDGH"
    b = "AEDFHR"
    dp, max_length = calculate_lcs_length(a,b)
    lcs_str = get_path(a, b, dp, len(a), len(b))
    print(lcs_str)

Output: ADH

I wonder if I could use one single method (without using recursion) to get the length and string both.

Is this code can be more reader friendly. I am not asking for one liner or complex optimization improve.

Reference: Longest common subsequence problem, From Wikipedia

Answer 1

Yes, you can easily convert the get_path function to an iterative version.

def get_path(a, b, dp, i, j): 
    seq = ""
    while(i != 0 and j != 0): 
        if a[i-1] == b[j-1]:
            i-=1
            j-=1
            seq += a[i]
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i-=1
            else:
                j-=1
    return seq[::-1]

And now you can merge this function with calculate_lcs_length into one if you want.

I guess you have read this, but I just want to remind you that all described optimizations are still applicable to your code.