沈阳网站建设,wordpress 优秀的博客主题简洁,济南便宜企业网站建设费用,网站打开慢 可以只换空间不换域名吗1. 题目 给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。 一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff08…1. 题目 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。 一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。 例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
2. 输入输出样例 示例 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 1000text1 和 text2 仅由小写英文字符组成。 3. 解题思想 动态规划步骤 1dp状态 dp[i][j]表示以text1[i]、text2[j]为结尾的两个字符串中最长公共子序列的长度 2状态转移方程 text1[i] text2[j]dp[i][j] dp[i - 1][j - 1] 1; text1[i] ! text2[j]max(dp[i - 1][j], dp[i][j - 1]); 3初始化状态 第0行第0列text1[0] text2[0]dp[0][0] 1text1[0] ! text2[0]dp[0][0] 0; 第0行text1[i] text2[0]dp[i][0] 1text1[i] ! text2[0]dp[i][0] dp[i - 1][0]; 第0列text1[0] text2[i]dp[0][1] 1text1[0] ! text2[i]dp[0][i] dp[0][i-1]; 4最优解 dp[n-1][m-1] 算法描述 核心思想是通过填充 dp 数组逐步构建最长公共子序列的长度考虑字符是否匹配。 首先获取输入字符串 text1 和 text2 的长度并创建一个二维数组 dp其大小为 (n1) x (m1)其中 n 和 m 分别是两个字符串的长度。dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。初始化 dp 数组的第一行和第一列遍历两个字符串的首字符如果它们相等将 dp[0][0] 设置为1否则将其保留为0。接着初始化第一行和第一列的其余部分以表示以 text1[0] 或 text2[0] 开头的子序列。使用两个嵌套循环遍历 text1 和 text2 的每个字符除去第一个字符填充 dp 数组。如果当前字符相同text1[i] text2[j]则将 dp[i][j] 设置为左上角的对角元素值加1表示找到了一个更长的公共子序列。如果当前字符不同将 dp[i][j] 设置为左边或上边的较大值表示要么继承左边的最长子序列长度要么继承上边的最长子序列长度。最终dp[n-1][m-1] 中存储的值即为 text1 和 text2 的最长公共子序列的长度。 4. 代码实现
// 定义一个函数该函数返回两个整数指针中的较大值
int max_(int *a, int *b) {// 比较两个指针的值返回较大的指针if (a b) {return a;}return b;
}// 定义一个计算两个字符串的最长公共子序列的函数
int longestCommonSubsequence(char *text1, char *text2) {// 获取字符串text1和text2的长度int n strlen(text1);int m strlen(text2);// 创建一个二维数组dp用于存储最长公共子序列的长度int dp[n][m];// 初始化dp数组将所有元素设置为0for (int i 0; i n; i) {for (int j 0; j m; j) {dp[i][j] 0;}}// 初始化dp数组的第一个元素if (text1[0] text2[0]) {dp[0][0] 1;}// 处理第一列初始化以text1[0]为开头的子序列for (int i 1; i n; i) {if (text1[i] text2[0]) {dp[i][0] 1;} else {dp[i][0] dp[i - 1][0];}}// 处理第一行初始化以text2[0]为开头的子序列for (int i 1; i m; i) {if (text1[0] text2[i]) {dp[0][i] 1;} else {dp[0][i] dp[0][i - 1];}}// 填充dp数组的其余部分找到最长公共子序列的长度for (int i 1; i n; i) {for (int j 1; j m; j) {if (text1[i] text2[j]) {// 如果字符相同将dp[i][j]设置为左上角值加1dp[i][j] dp[i - 1][j - 1] 1;} else {// 如果字符不相同将dp[i][j]设置为左边和上边的较大值dp[i][j] max_(dp[i - 1][j], dp[i][j - 1]);}}}// 返回dp数组的最右下角元素即最长公共子序列的长度return dp[n - 1][m - 1];
}5. 复杂度分析 时间复杂度分析 初始化 dp 数组的两个嵌套循环for 循环嵌套需要遍历整个数组时间复杂度为O(n * m)其中 n 和 m 分别是 text1 和 text2 的长度。接下来还需要一个嵌套循环来填充 dp 数组这个循环也需要遍历整个 dp 数组时间复杂度为O(n * m)。总的时间复杂度是O(n * m n * m)即O(n * m)。 算法的时间复杂度是 O(n * m)其中 n 和 m 分别是输入字符串 text1 和 text2 的长度。 空间复杂度分析 dp 数组的空间复杂度是O(n * m)因为它是一个二维数组其大小与输入字符串的长度相关。 综上所述这段代码的空间复杂度是 O(n * m)时间复杂度是 O(n * m) 力扣LeetCode官网 - 全球极客挚爱的技术成长平台https://leetcode.cn/problems/qJnOS7/submissions/
