#1143

Longest Common Subsequence

medium· 2-D DPruns: 0

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is generated from the original string by deleting some characters (possibly none) without changing the relative order of the remaining characters. If there is no common subsequence, return 0.

wpm 0acc 100%time 0:000 / 472

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

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.