Skip to content

Instantly share code, notes, and snippets.

@thmain
Created November 8, 2024 15:37
Show Gist options
  • Save thmain/2926db6b39ba3ebd37e14ab0375ac20e to your computer and use it in GitHub Desktop.
Save thmain/2926db6b39ba3ebd37e14ab0375ac20e to your computer and use it in GitHub Desktop.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# Use a dictionary for memoization
dp = {}
return self.solve(text1, text2, 0, 0, dp)
def solve(self, text1, text2, i, j, dp):
# Base case: if we reach the end of either string, LCS length is 0
if i >= len(text1) or j >= len(text2):
return 0
# Memoization key based on indices instead of substrings
key = (i, j)
# Check if result is already computed
if key in dp:
return dp[key]
# Recursive cases
if text1[i] == text2[j]:
dp[key] = 1 + self.solve(text1, text2, i + 1, j + 1, dp)
else:
option1 = self.solve(text1, text2, i + 1, j, dp)
option2 = self.solve(text1, text2, i, j + 1, dp)
dp[key] = max(option1, option2)
return dp[key]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment