Longest Common Subsequence

Medium

Python

def lcs(text1,text2):
    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]

Java

public int longestCommonSubsequence(String t1,String t2){
    int m=t1.length(),n=t2.length();
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=t1.charAt(i-1)==t2.charAt(j-1)?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}

Key Insight

2D DP. Python list comprehension vs Java 2D array. charAt() vs indexing.

Python → Java Differences

2D list comprehension vs 2D array
text1[i-1] vs charAt()
DP transition identical

Python

def lcs(text1,text2):
    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]

Java

public int longestCommonSubsequence(String t1,String t2){
    int m=t1.length(),n=t2.length();
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=t1.charAt(i-1)==t2.charAt(j-1)?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}

Algorithm Steps

1. 2D table
2. Match: diagonal+1
3. Mismatch: max of top/left

← Previous All Dynamic Programming Next →