[Leetcode] Longest Common Subsequence
Classic two dimensional dp problem.
Description
Given two strings text1
and text2
, return the length of their longest common subsequence. If there is no common subsequence, return 0
.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example,
"ace"
is a subsequence of"abcde"
.
A common subsequence of two strings is a subsequence that is common to both strings.
Examples
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Solution
Imagine a matrix where char of text1 filled in top of each row, and char of text2 filled in top of each col.
# abcde
# ^
# ace
# ^
# X A C E [0 0 0 0]
# A [0 1 1 1]
# B [0 1 1 1]
# C [0 1 2 2]
# D [0 1 2 2]
# E [0 1 2 3]
dp[i][j] represents lcs for text1[:i] & text2[:j]
When forwarding new, inherit value from up left / up / left. When new common char founded, use up left (exclude new for both) and increment 1 as this new common enable two to increase lcs of 1 len. When not common char, use up and left (respectively one with new and one without new) and inherit the larger one. e.g. [5][1] lcs(ABCDE, A) = 1 with [4][2] lcs(ABCD, AC) = 2 -> [5][2] lcs(ABCDE, AC) = 2
- code