Medium

Longest Common Subsequence

065

Return the length of the longest subsequence common to text1 and text2.

EXAMPLES

Example 1

Input
{
  "text1": "abcde",
  "text2": "ace"
}

Output
3

FUNCTION SHAPE

text1: stringtext2: string→int

SOLUTION NOTE

If characters match, extend LCS by 1. Otherwise, try excluding character from either string and take the max.

Reveal reference solution +

pythonREFERENCE

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    @cache
    def dp(i, j):
        if i < 0 or j < 0: return 0
        if text1[i] == text2[j]:
            return 1 + dp(i-1, j-1)
        return max(dp(i-1, j), dp(i, j-1))

    return dp(len(text1)-1, len(text2)-1)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗