我认为你可以使用一种非常优雅的动态规划算法来解决这个问题,它的时间复杂度为O(mn),空间复杂度也是O(mn),其中m和n是每个字符串中字符的数量。这个想法基于以下递归公式。假设两个字符串为A = a
0 a
1 a
2 ... a
n-1和B = b
0 b
1 b
2 ... b
m-1,并查看它们的第一个字符a
0和b
0。那么有三种方法可以尝试找到最长的公共子序列:
- 如果第一个字符相等,则一种选择是找到其余两个字符串的最长公共子序列,然后将第一个字符添加到匹配中。
- 或者,您可以决定不匹配前两个字符。在这种情况下,一种选择是查看忽略第一个字符串的第一个字符时可以制作的最长公共子序列。
- 最后,您还可以忽略第二个字符串的第一个字符。
这给了我们一个非常好的递归公式:
LCS(A[0 .. n], B[0 .. m]) = longest of {
A[0] + LCS(A[1 .. n], B[1 .. m]) (if A[0] == B[0]),
LCS(A[1 .. n], B[0 .. m]),
LCS(A[0 .. n], B[1 .. m])
}
作为我们的基本情况,任何字符串与空字符串的最长公共子串都是空字符串:
LCS (A[n .. n], B[i, m]) = ""
LCS (A[i .. n], B[m, m]) = ""
这里的“最长公共子串”的定义允许你计算出 LCS(A[i..n], B[j..m]) 的值,只要给定三个值:LCS(A[i+1..n], B[j+1..m])、LCS(A[i..n], B[j+1..m]) 和 LCS(A[i+1..n], B[j..m])。因此,如果按正确顺序计算这些值,你可以在一次遍历中将结果填入表格并构造出结果。利用一些标准 DP 技巧,可以将其运行时间降至 O(mn)。