# Longest Common Subsequence | LeetCode | Solution Explained

Longest Common Subsequence. One of the most popular string DP questions. I explain the logic with recursive & iterative dynamic programming approach coded in Python3.

Problem: https://leetcode.com/problems/longest-common-subsequence/

**Contents**hide

## Logic

- Let
`s`

and`t`

be source and target sentences - These are the same as
`text1`

and`text2`

- Each character is either a part of the answer OR it is not
- Have two pointers i, j pointing to s and t respectively
- if
`s[i] == t[j]`

,- we have a match, thus its a good idea to include this character

- if not,
- we try skipping over the character in
`s`

by doing`i+1`

or do skip over character in`t`

by doing`j+1`

- we try skipping over the character in
- we don’t know which is the better case, so we spawn a recursion in both cases and store the max(case1, case2)

## Recursive Solution

class Solution: def longestCommonSubsequence(self, s: str, t: str) -> int: @lru_cache(None) def recurse(i, j): if i >= m or j >= n: return 0 if s[i] == t[j]: return 1 + recurse(i+1, j+1) return max(recurse(i+1, j), recurse(i, j+1)) m, n = len(s), len(t) return recurse(0, 0)

## Iterative Solution

We can now just convert the iterative logic into recursive logic.

class Solution: def longestCommonSubsequence(self, s: str, t: str) -> int: m, n = len(s), len(t) dp = [[0] * (n+1) for _ in range(m+1)] for i in reversed(range(m)): for j in reversed(range(n)): if s[i] == t[j]: dp[i][j] = 1 + dp[i+1][j+1] else: dp[i][j] = max(dp[i+1][j], dp[i][j+1]) return dp[0][0]

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022