Longest Common Subsequence
Problem Description
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is derived by deleting some characters without changing order.
Example 1:
Input: text1="abcde", text2="ace"
Output: 3 ("ace")
Example 2:
Input: text1="abc", text2="abc"
Output: 3
Example 3:
Input: text1="abc", text2="def"
Output: 0
DE Shaw Tier 3 — LC 1143.
DP O(m*n): dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1].
If chars match: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Can optimize to O(min(m,n)) space.
Example Test Cases
Example 1
Input: ["abcde","ace"]
Expected: 3
Example 2
Input: ["abc","abc"]
Expected: 3
Example 3
Input: ["abc","def"]
Expected: 0
Example 4
Input: ["oxcpqrsvwf","shmtulqrypy"]
Expected: 2
Run your code to see the results