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/

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 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]

    Leave a Reply

    Your email address will not be published. Required fields are marked *