0. 前言
动态规划算法常常被用于处理字符串相关的问题,其中最经典的就是最长公共子序列和最长公共子串问题。
1. 问题描述
最长公共子序列(Longest Common Sequence)
给定两个字符串,求出它们之间最长的相同子序列的长度。如:字符串1:BDCABA;字符串2:ABCBDAB,则最长公共子序列是:BCBA,长度为4。
最长公共子串(Longest Common Substring)
给定两个字符串,求出它们之间最长的相同子字符串的长度。如:字符串1:DVBGHRF,字符串2:ABGHRCD,则最长公共子串为:BGHR,长度为4。
子序列和子串的区别在于:子序列要求字符可以不连续,子串要求字符连续
下面使用动态规划的方法进行求解,最长公共子串和最长公共子序列在不引起混淆的情况下简称为LCS。
2. 最长公共子串问题求解
暴力解法:方便对比,时间复杂度O(n^3),空间复杂度O(1):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
26public int lcs_n3(String str1, String str2) {
int len1 = str1.size();
int len2 = str2.size();
if (size1 == 0 || size2 == 0) return 0;
// 长度
int result = 0;
for (int i = 0; i < len1; ++i) {
for (int j = 0; j < len2; ++j) {
int length = 0;
int m = i;
int n = j;
while(m < len1 && n < len2) {
if (str1[m] != str2[n]) break;
++length;
++m;
++n;
}
if (result < length) {
result = length;
}
}
}
}
动态规划的关键是把问题分解成一个个规模更小的关联的子问题(状态转移方程),直到到达边界条件或已知条件(初始状态)
动态规划
设dp[i][j]为字符串 [a1,a2,…,ai]与字符串[b1,b2,…,bj]的最长公共连续子串的最后一个字符与这个两个字符串的最后一个字符相等的情况下,这个LCS的长度
初始状态:
显然dp[0][0] = 0,而且第一列和第一行(str1或str2长度为0)也为0
状态转移方程:
- dp[i][j] = 0, str1[i] != str2[j]
- dp[i][j] = dp[i - 1][j - 1] + 1, str1[i] = str2[j]
时间复杂度O(n^2),空间复杂度O(n^2)
实例:
str1:ABGHRCD str2:DVBGHRF
str1\str2 | “” | D | V | B | G | H | R | F |
---|---|---|---|---|---|---|---|---|
“” | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
B | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
G | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
H | 0 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |
R | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 |
C | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
D | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public int lcs_dp(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int result = 0; //记录最长公共子串长度
int c[][] = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
for( int j = 0; j <= len2; j++) {
if(i == 0 || j == 0) {
c[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
c[i][j] = c[i - 1][j - 1] + 1;
result = max(c[i][j], result);
} else {
c[i][j] = 0;
}
}
}
return result;
}
3. 最长公共子序列问题求解
最长公共子序列和最长公共子串的差异,本质上体现在子字符串是否连续,因此也造成了dp数组的意义不同。
设dp[i][j]为最长公共子序列的长度(和最长公共子串的dp数组不一样),显然dp[str1.size()][str2.size()]就是所求结果
初始状态:
显然dp[0][0] = 0,而且第一列和第一行(str1或str2长度为0)也为0
状态转移方程:
- dp[i][j] = dp[i - 1][j - 1] + 1, str1[i] = str2[j]
- dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]), str1[i] != str2[j]
时间复杂度O(n^2),空间复杂度O(n^2)
实例:
str1:ABCBDAB str2:BDCABA
str1\str2 | “” | B | D | C | A | B | A |
---|---|---|---|---|---|---|---|
“” | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
B | 0 | 1 | 2 | 3 | 3 | 4 | 4 |
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static int lcs_dp(String str1, String str2){
int[][] c = new int[str1.length() + 1][str2.length() + 1];
for(int row = 0; row <= str1.length(); row++)
c[row][0] = 0;
for(int column = 0; column <= str2.length(); column++)
c[0][column] = 0;
for(int i = 1; i <= str1.length(); i++)
for(int j = 1; j <= str2.length(); j++)
{
if(str1.charAt(i - 1) == str2.charAt(j - 1))
c[i][j] = c[i - 1][j - 1] + 1;
else if(c[i][j - 1] > c[i - 1][j])
c[i][j] = c[i][j - 1];
else
c[i][j] = c[i - 1][j];
}
return c[str1.length()][str2.length()];
}
4. 总结
重点再说一遍:子序列和子串的区别在于:子序列要求字符可以不连续,子串要求字符连续
动态规划通过空间换时间,实际上上述的解法还可以进一步压缩空间复杂度到O(1),这里不作讲解。
Copyright © 2018, GDUT CSCW back-end Kanarien, All Rights Reserved