# 最长公共子序列

最长公共子序列

  • 最长公共子序列,即 Longest Common Subsequnce,LCS
  • 一个序列S任意删除若干个字符得到的新序列T,则T叫做S的子序列
  • 两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列
    • 字符串13455和245576的最长公共子序列为455
    • 字符串acdfg与adfc的最长公共子序列为adf
  • 注意区别最长公共子串(Longest Common Substring),最长公共子串要求连续
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

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

示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace",它的长度为 3

示例 2:
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc",它的长度为 3

示例 3:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0

提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 方法1: 暴力求解,穷举法

/**
 * 方法一: 暴力求解,穷举法
 * 假定字符串X,Y的长度分别为m, n
 * X 的一个子序列即下标序列{1, 2, ..., m}的严格递增子序列,因此X共有 2^m 个不同的子序列,同理Y有2^n个不同子序列,从而穷举搜索法需要指数时间 O((2^m)*(2^n))
 * 对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否X和Y的公共子序列,并且在检查过程中选出最长的公共子序列
 * 显然,不可取(复杂,还不好做,因为要穷举)
 */
1
2
3
4
5
6
7