Dynamic Programming· 25 min

Longest Common Subsequence

Find LCS of two strings using DP table

Setup

s1:s2:
Step 1 / 72

Current step

1 / 72

Initialize DP table. Row 0 and column 0 = 0 (empty string has no common subsequence). Compare "ABCBDAB" (rows) with "BDCAB" (columns).

Step log

s1 \ s2∅BDCAB
∅000000
A0·····
B0·····
C0·····
B0·····
D0·····
A0·····
B0·····
Computing now
Dependencies used
Filled
Empty
lcs.java
1int lcs(String s1, String s2) {
2    int m = s1.length(), n = s2.length();
3    int[][] dp = new int[m+1][n+1];
4    for (int i = 1; i <= m; i++) {
5        for (int j = 1; j <= n; j++) {
6            if (s1.charAt(i-1) == s2.charAt(j-1))
7                dp[i][j] = dp[i-1][j-1] + 1;
8            else
9                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
10        }
11    }
12    return dp[m][n];
13}
● Java

Longest Common Subsequence

Given two strings, find the length of their longest common subsequence (not necessarily contiguous). dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1].

Time
O(m·n)
Space
O(m·n)
Rows
8
Cols
6
38 / 46