给定两个字符串text1和text2,计算它们的最长公共子序列的 长度。 实验内容 输入:字符串textl和 text2,长度范围为1≤ textl.length, text2, length ≤ 1
时间: 2024-11-22 21:41:56 浏览: 11
给定两个字符串 `text1` 和 `text2`,计算它们的最长公共子序列(Longest Common Subsequence, LCS)是指在不改变顺序的情况下,这两个字符串中最长的共享字符序列。这个任务通常通过动态规划算法来解决,最经典的是用一个二维数组来记录每个位置上两个字符串的公共子序列长度。
以下是计算最长公共子序列长度的基本步骤:
1. 初始化一个二维数组 `dp`,其中 `dp[i][j]` 存储 `text1` 的前 i 个字符和 `text2` 的前 j 个字符的最长公共子序列长度。
2. 遍历两个字符串的每个字符:
- 如果 `text1[i-1]` 等于 `text2[j-1]`,那么 `dp[i][j] = dp[i-1][j-1] + 1`,因为当前字符可以添加到最长公共子序列中;
- 否则,如果 `text1[i-1]` 和 `text2[j-1]` 不同,取 `dp[i-1][j]` 和 `dp[i][j-1]` 中的最大值作为 `dp[i][j]`,表示删除其中一个字符后找到的最长子序列长度。
3. 最终,`dp[text1.length()][text2.length()]` 就是 `text1` 和 `text2` 的最长公共子序列的长度。
例如,如果你有 `text1 = "ABCDGH"` 和 `text2 = "AEDFHR"`, 最终的 `dp` 数组会像下面这样填充:
```
A E D F H R
0 0 0 0 0 0 0
A 1 1 1 1 1 1
B 0 1 1 1 1 1
C 0 0 1 1 1 1
D 0 0 0 2 2 2
G 0 0 0 0 3 3
H 0 0 0 0 0 4
```
所以,`text1` 和 `text2` 的最长公共子序列长度是 4("ADFH" 或 "AEHR"),分别对应于左下角的 `dp[4][4]`。
阅读全文