Sign up to mark as complete
Sign up to bookmark this question

# Longest Common Subsequence (LCS)

You're given two sequences of integers. Your task is to write a function that finds the Longest Common Subsequence (LCS) of the two sequences.

Return a list of integers representing the Longest Common Subsequence of seq1 and seq2.

Given the sequences seq1 = [1, 2, 3, 4, 5] and seq2 = [6, 7, 1, 2, 8], your function should return [1, 2].

```
def find_lcs(seq1: list, seq2: list) -> list:
```

pass

**Inputs**- seq1: A list of integers representing the first sequence.
- seq2: A list of integers representing the second sequence.

**Output**Return a list of integers representing the Longest Common Subsequence of seq1 and seq2.

**Example**Given the sequences seq1 = [1, 2, 3, 4, 5] and seq2 = [6, 7, 1, 2, 8], your function should return [1, 2].

Hint

Make use of a Dynamic Programming table (DP table). It's a data structure, often implemented as a 2D array (or sometimes higher dimensions depending on the problem), used to store intermediate results of subproblems so that they can be reused later. This is a key aspect of dynamic programming that helps to improve computational efficiency by avoiding redundant calculations.

In the context of the Longest Common Subsequence (LCS) problem, the DP table

`dp`

is a 2D array where `dp[i][j]`

stores the length of the LCS of the prefixes `seq1[0..i-1]`

and `seq2[0..j-1]`

. This table is filled iteratively based on the relations between smaller subproblems, and the final answer is constructed by backtracking through this table. The use of a DP table allows us to solve the problem in way less time compared to using a different naive recursive approach.
Solution

```
# Implementing the Longest Common Subsequence (LCS) using Dynamic Programming
```

def find_lcs(seq1, seq2):

n = len(seq1)

m = len(seq2)

# Initialize a DP table with zeros

dp = [[0] * (m + 1) for _ in range(n + 1)]

# DP step: fill in the table

for i in range(1, n + 1):

for j in range(1, m + 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])

# Reconstruct the LCS

lcs = []

i, j = n, m

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 lcs[::-1] # Reverse the LCS to get it in the correct order

# Test the function

seq1 = [1, 2, 3, 4, 5]

seq2 = [6, 7, 1, 2, 8]

print(find_lcs(seq1, seq2)) # Should return [1, 2]

Related Questions

Title | Category | Subcategory | Difficulty | Status |
---|---|---|---|---|

Common Prefix | Programming | Medium | Medium | |

Consecutive Letters | Programming | Medium | Medium | |

Drawing a Blue 3 | Programming | Medium | Medium | |

Empty # Boxes | Programming | Medium | Medium | |

Group Anagrams | Programming | Medium | Medium | |

Last Node of Singly Linked List | Programming | Medium | Medium | |

Optimal Stopping Strategy | Programming | Medium | Medium | |

Palindrome Checker | Programming | Medium | Medium | |

Pricing Accuracy | Programming | Medium | Medium | |

Prime Number Generator | Programming | Medium | Medium | |

Roulette Table | Programming | Medium | Medium | |

Subarray Sum Equals Zero | Programming | Medium | Medium | |

Top 2000 Songs | Programming | Medium | Medium | |

Words in String | Programming | Medium | Medium |

Discussion

Please log in to see the discussion.