最长公共子序列

发表于 | 更新于: | 分类于 |
字数统计: 935 字 | 阅读时长 ≈ 3 分钟

这一类最长公共子序列问题属于二维数组动态规划的典型题目，非常经典所以做一下笔记。

首先是题干部分：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

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

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 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, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看见这种子序列啊，最长什么的，条件反射就会想到动态规划上，进而转到研究状态转化与条件。

这里我们很清晰地认识到任一个字母最长的子序列长度取决于他之前字母的最长子序列。很显然，两组字符串做动态规划，一维数组基本不太可能满足需求了，这个时候就需要用上二维数组。

table

这里解释一下为什么表格第一行与第一列都要用0填满了——实际上这是防止边际判断和出界的一种方式（说白了就是懒，不这么搞也行就是麻烦点）。

表格的使用其实很简单：每次拿单行与不同列比较，遇到相同字母就将【当前位置的数】=【左上单元格的数】+1，否则就【当前位置的数】=MAX（【左边单元格的数】，【上边单元格的数】）。然后最后一行最后一列的元素就是答案啦。

不过这样的使用其实是有重要的含义的，比如【左上单元格的数】其实就是到当前列对应字母上一个字母时最长公共子序列长度，因此在当前已确定字母相同时，+1就相当于更新了当前最长公共子序列长度。

再说MAX（【左边单元格的数】，【上边单元格的数】）的含义，这其实就是一个状态转移方程的一部分（上面那个也是，欸嘿），优先选取最长的可能（与背包问题类似，都是动态规划）。

代码如下：

\

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define max(a,b) ( ((a)>(b)) ? (a):(b) )

int longestCommonSubsequence(char* text1, char* text2) {

  int max=0;

  int** table=malloc(sizeof(int*)*(strlen(text1)+1));

  for(int i=0;i<strlen(text1)+1;i++){

​    table[i]=malloc(sizeof(int)*(strlen(text2)+1));

​    table[i][0]=0;

  }

  for(int i=0;i<strlen(text2)+1;i++)

  table[0][i]=0;

  for(int i=1;i<strlen(text1)+1;i++){

​    for(int j=1;j<strlen(text2)+1;j++){

​      if(text1[i-1]==text2[j-1])

​      table[i][j]=table[i-1][j-1]+1;

​      else

​      table[i][j]=max(table[i-1][j],table[i][j-1]);

​    }

  }

  return table[strlen(text1)][strlen(text2)];

}


主要还是要多多锻炼，动态规划有时候感觉是真的阴间OMO

最后放一张女儿在这里o(*≧▽≦)ツ┏━┓：

KLEE