6
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.