## Longest Common Subsequence

Leetcode 1143

LCS Problem Statement: Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Input sample:

text1 = "abcde", text2 = "ace"


Sample output:

3


## Solution:

State representation:

• dp[i][j] is the length of LCS of text1[0 ~ i-1] and text2[0 ~ j-1]

State calculation:

• text1[i - 1] == text2[j - 1] : add the value of text1[i - 1] to the end of the LCS, as both strings have this value with dp[i - 1][j - 1] + 1
• text1[i - 1] != text2[j - 1] : don’t include it in the LCS, look at dp[i - 1][j] and dp[i][j - 1]