LeetCode 1143: Longest Common Subsequence — Step-by-Step Visual Trace

Medium — Dynamic Programming | String | Two Pointers The Problem Find the length of the longest common subsequence (LCS) between two strings, where a subsequence maintains the relative order of characters but doesn't need to be contiguous. Approach Use dynamic programming with a 2D table where dp[i][j] represents the LCS length of the first i characters of text1 and first j characters of text2. If characters match, add 1 to the diagonal value; otherwise, take the maximum of the left or top cell. Time: O(m*n) · Space: O(m*n) Code class Solution : def longestCommonSubsequence ( self , text1 : str , text2 : str ) -> int : m , n = len ( text1 ), len ( text2 ) # Create a 2D dp array of size (m+1) x (n+1) and initialize it with zeros. dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] # Fill in the dp array using dynamic programming. 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 ]