1143. Longest Common Subsequence¶
题目信息¶
- 题号:
1143
- 难度:
Medium
- 主题:
字符串、子序列、动态规划
- 原题:
- 重点:
公共子序列必须在两个字符串中保持字符相对顺序,但不要求连续;不存在公共字符时返回
0
题目重述¶
给定两个小写字符串 text1 和 text2。从字符串中删除任意数量的字符但不改变剩余字符的相对顺序,可以得到一个子序列。
请返回两个字符串最长公共子序列的长度。公共子序列可以不连续;若两个字符串没有任何非空公共子序列,返回 0。
1 <= text1.length, text2.length <= 1000,两个字符串只包含小写英文字母。
自建示例¶
最长结果可以不连续:
输入:text1 = "abc", text2 = "bac"
输出:2
解释:"ac" 和 "bc" 都是长度为 2 的公共子序列,不存在长度为 3 的公共子序列。
没有公共字符:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有相同字符,因此不存在非空公共子序列。