编辑距离 题目来源:Leetcode
1、问题描述
给定两个字符串word1和word2,返回转换为所需的最少操作数word1word2。
您可以对单词进行以下三个操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
文章图片
2、思路分析
文章图片
文章图片
3、代码实现
class Solution {
public:
int minDistance(string word1, string word2) {
int len1=word1.size();
int len2=word2.size();
vector> v(len1+1,vector(len2+1));
for(int i=0;
i<=len1;
i++)
v[i][0]=i;
for(int i=0;
i<=len2;
i++)
v[0][i]=i;
for(int i=1;
i<=len1;
i++){
for(int j=1;
j<=len2;
j++){
//在删除拆入选一个最小的
v[i][j]=min(v[i][j-1],v[i-1][j])+1;
//最后一个字符相等就不需要替换字符
if(word1[i-1]==word2[j-1]){
//不需要操作,从v[i][j]也就是在删除,替换中选出最小的中和(i-1,j-1)选一个最小的
v[i][j]=min(v[i][j],v[i-1][j-1]);
}else{
//需要替换字符
//需要操作,从v[i][j]也就是在删除,替换中选出最小的中和(i-1,j-1)+1加一也就是在前i-1次操作后还需要替换一次选一个最小的
v[i][j]=min(v[i][j],v[i-1][j-1]+1);
}
}
}return v[len1][len2];
}
};
不同的子序列 题目来源:Leetcode
1、问题描述
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)
示例:
文章图片
2、思路解析
文章图片
文章图片
3、代码实现
class Solution {
public:
int numDistinct(string s, string t) {
intlen1=s.size();
int len2=t.size();
vector> v(len1+1 ,vector(len2+1,0));
//T为空字符但是字串个数还是1
for(int i=0;
i<=len1;
i++){
v[i][0]=1;
}
for(int i=1;
i<=len1;
i++){
for(int j=1;
j<=len2;
j++){
if(s[i-1]==t[j-1]){
//相等使用第i个字符和不使用前i个字符
v[i][j]=v[i-1][j-1]+v[i-1][j];
}else{
//不相等退化为在s前i-1找T的前j个字符
v[i][j]=v[i-1][j];
}
}
}
return v[len1][len2];
}
};
推荐阅读
- 数据结构学习指导|数据结构初阶(八大排序)
- 数据结构|【初阶数据结构】完全二叉树实现堆排序
- 数据结构|【数据结构初阶】(堆的接口实现和堆排序)
- c语言|《校招大厂中等难度笔试题》纯C语言求解迷宫问题——进来测测你数据结构初阶学的怎么样()
- 初阶数据结构与算法|【初阶数据结构与算法】第七篇(二叉树和堆的基本概念+以及堆的实现)
- 数据结构|二叉树初阶1、
- 蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解(C语言/C++)
- 蓝桥杯题解|蓝桥杯“字串排序“题解
- #|<<算法很美>>——(七)——DFS典题(二):数独游戏