Given two strings X and Y, write a program to return the length of their longest common subsequence.
Problem Note
- 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, "prt" is a subsequence of "pqrst" while "ptr" 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.
- The input strings consist of lowercase English characters only.
Example 1
Input: X = "pqrst", Y = "prt"
Output: 3
Explanation: The longest common subsequence is "prt" and its length is 3.
Example 2
Input: X = "pqr", Y = "pqr"
Output: 3
Explanation: The longest common subsequence is "pqr" and its length is 3.
Example 3
Input: X = "pqr", Y = "stu"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.