展示产品的网站 个人备案还是企业,网站建设毕业设计中期报告,如何查询网站以建设多长时间,服务商平台登录文章目录 最长公共子序列题目描述问题分析程序代码复杂度分析 最短编辑距离题目描述问题分析程序代码复杂度分析 编辑距离题目描述输入格式输出格式 问题分析程序代码 最长公共子序列
题目描述 原题链接 给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共… 文章目录 最长公共子序列题目描述问题分析程序代码复杂度分析 最短编辑距离题目描述问题分析程序代码复杂度分析 编辑距离题目描述输入格式输出格式 问题分析程序代码 最长公共子序列
题目描述 原题链接 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
问题分析
这里假设text1和text2的下标均从 1 开始
状态定义dp[i][j]表示text1[1...i]和text2[1...j]的最长公共子序列的长度
状态划分根据text1[i]和text2[j]是否在最长公共子序列中可以将状态划分为四类
text1[i]在text1[j]也在dp[i][j] dp[i-1][j-1] 1同时要求text1[i] text2[j]text1[i]在text1[j]不在dp[i][j] dp[i][j-1]text1[i]不在text1[j]在dp[i][j] dp[i-1][j]text1[i]不在text1[j]也不在dp[i][j] dp[i-1][j-1]
由于情况 4 包含在情况 2 和情况 3 中因此不需要要单独考虑最终可以得到如下的状态计算。
状态计算
若text1[i] text2[j]dp[i][j] dp[i-1][j-1] 1若text1[i] ! text2[j]dp[i][j] max(dp[i][j-1], dp[i-1][j])
程序代码
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n text1.size(), m text2.size();vectorvectorint dp(n 1, vectorint(m 1, 0));text1 text1;text2 text2;for(int i 1; i n; i) {for(int j 1; j m; j) {dp[i][j] max(dp[i-1][j], dp[i][j-1]);if( text1[i] text2[j] ) {dp[i][j] max(dp[i][j], dp[i-1][j-1] 1);}}}return dp[n][m];}
};复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
最短编辑距离
题目描述 原题链接 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
问题分析
这里假设word1和word2的下标均从 1 开始
状态定义dp[i][j]表示将word1[1...i]变成word2[1...j]所需的最少操作次数
状态计算dp[i][j]可能从三种可能状态转移过来三种状态取最小值
删除操作删除word1[i]使得 word1 和 word2 匹配即dp[i][j] dp[i-1][j] 1插入操作在word1的末尾插入word2[j]使得二者匹配即dp[i][j] dp[i][j-1] 1替换操作word1[1...i-1]与word2[1...j-1]匹配word1[i]和word2[j]有两种情况 若word1[i] word2[j]则无需进行替换操作即dp[i][j] dp[i-1][j-1]若word1[i] ! word2[j]则需进行替换操作即dp[i][j] dp[i-1][j-1] 1
边界情况
dp[0][0]二者都为空无需进行任何操作即dp[0][0] 0dp[0][i]表示word1为空word1只能通过插入操作变成word2即dp[0][i] idp[i][0]表示word2为空word1只能通过删除操作变成word2即dp[i][0] i
程序代码
class Solution {
public:int minDistance(string word1, string word2) {int n word1.size(), m word2.size();int maxVal m n; // 初始化数组word1 word1;word2 word2;vectorvectorint dp(n 1, vectorint(m 1, maxVal));// 边界情况dp[0][0] 0;for(int i 1; i m; i) {dp[0][i] i;}for(int i 1; i n; i) {dp[i][0] i;}for(int i 1; i n; i) {for(int j 1; j m; j) {// 删除和插入操作dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1);// 替换操作if(word1[i] word2[j]) {dp[i][j] min(dp[i][j], dp[i-1][j-1]);}else {dp[i][j] min(dp[i][j], dp[i-1][j-1] 1);}}}return dp[n][m];}
};复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
编辑距离
题目描述
给定 n 个长度不超过 10 的字符串以及 m 次询问每次询问给出一个字符串和一个操作次数上限。
对于每次询问请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行每行包含一个字符串表示给定的字符串。
再接下来 m 行每行包含一个字符串和一个整数表示一次询问。
字符串中只包含小写字母且长度均不超过 10。
输出格式
输出共 m 行每行输出一个整数作为结果表示一次询问中满足条件的字符串个数。
问题分析
本质上其实就是最短编辑距离问题
程序代码
#include iostream
#include algorithm
using namespace std;int n, m;
const int N 1010, INF 1e9 7;
string s[N];
string p;
int k;int solve(string a, string b)
{int n a.size(), m b.size();a a;b b;vectorvectorint dp(n 1, vectorint(m 1, INF));// 边界情况dp[0][0] 0;for(int i 1; i m; i) {dp[0][i] i;}for(int i 1; i n; i) {dp[i][0] i;}for(int i 1; i n; i) {for(int j 1; j m; j) {// 删除和插入操作dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1);// 替换操作if(a[i] b[j]) {dp[i][j] min(dp[i][j], dp[i-1][j-1]);}else {dp[i][j] min(dp[i][j], dp[i-1][j-1] 1);}}}return dp[n][m];
}int main()
{cin n m;for(int i 0; i n; i) {cin s[i];}for(int i 0; i m; i) {cin p k;int cnt 0;for(int j 0; j n; j) {if( solve(s[j], p) k ) cnt;}printf(%d\n, cnt);}return 0;
}
