1143. Longest Common Subsequence

题目信息

题号:

1143

难度:

Medium

主题:

字符串、子序列、动态规划

原题:

LeetCode 1143

重点:

公共子序列必须在两个字符串中保持字符相对顺序,但不要求连续;不存在公共字符时返回 0

题目重述

给定两个小写字符串 text1 和 text2。从字符串中删除任意数量的字符但不改变剩余字符的相对顺序,可以得到一个子序列。

请返回两个字符串最长公共子序列的长度。公共子序列可以不连续;若两个字符串没有任何非空公共子序列,返回 0。

1 <= text1.length, text2.length <= 1000,两个字符串只包含小写英文字母。

自建示例

最长结果可以不连续:

输入:text1 = "abc", text2 = "bac"
输出:2
解释:"ac" 和 "bc" 都是长度为 2 的公共子序列,不存在长度为 3 的公共子序列。

没有公共字符:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有相同字符,因此不存在非空公共子序列。