给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

提示:

1 <= text1.length <= 1000

1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

解题思路

1,注意是最长公共子序列,不是最长公共子串

2,最长公共子序列问题是经典的动态规划题

3,状态转移方程

A,若str1[i]==str2[j],则str1[:i]和str2[:j]最长公共子序列的长度为

str1[:i-1]和str2[:j-1]最长公共子序列的长度加一

B, str1[:i-1]和str2[:j], str1[:i]和str2[:j-1]两者中较长者

4,未来表示方便,存储数组长度比字符串长度多1

代码实现