Algorithm of the day -

The Longest Common Subsequence with Dynamic Programming

Summary

This algorithm is used to find the longest common subsequence between two sequences, it uses dynamic programming to build a 2D matrix where each cell contains the length of the longest common subsequence up to that point

Use Case

This algorithm can be used in data comparison, for example, to compare two versions of a document and highlight the differences.

Steps

  1. Initialize a 2D matrix with dimensions (m+1) x (n+1) where m and n are the lengths of the two sequences.
  2. Fill the first row and first column of the matrix with zeros.
  3. Compare each element of the first sequence with each element of the second sequence and fill the matrix accordingly.
  4. Build the longest common subsequence by tracing back the matrix from the bottom right corner.

Complexity

The time complexity of this algorithm is O(m*n) and the space complexity is also O(m*n) where m and n are the lengths of the two sequences.

Code Example

def longest_common_subsequence(seq1, seq2):
    m = len(seq1)
    n = len(seq2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if seq1[i - 1] == seq2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if seq1[i - 1] == seq2[j - 1]:
            lcs.append(seq1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(lcs))