longestCommonSubsequence.py

from functools import lru_cache

class Solution:
    
    def longestCommonSubsequence(self, word1: str, word2: str) -> int:  
    
        @lru_cache(None)
        def dfs(i, j):
            if i == len(word1) or j == len(word2):
                return 0
            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1) + 1
            else:
                return max(dfs(i, j + 1), dfs(i + 1, j))
    
        return dfs(0, 0)