没有合适的资源?快使用搜索试试~ 我知道了~
字符串操作,将一个字符串变换为另一个字符串。供自己参考。
资源推荐
资源详情
资源评论
给定两个字符串Str1和Str2,还有三个整数a,b,c,现在规定插入一个字符的代价是a,删除一个字符的代价是b,替换一个字符的代价是c,现在想要将Str1转化为Str2,求转化的最小代价。
例如:
Str1="ac";
Str2="abc";
a = 5
b = 3
c = 2
最好的转化路径为在Str1中的a和c中间直接插入一个b即可完成转化,所以最小代价为5。
Str1="ab";
Str2="bb";
a = 5
b = 4
c = 3
最好的转化路径为将Str1中的a直接替换成b即可完成转化,所以最小代价为3。
进阶:如果Str1的长度为M,Str2的长度为N,你的代码需优化到在时间复杂度不低于O(M*N)的情况下,额外空间复杂度为O(Min{M,N})
解答:
难度:尉
进阶难度:校
先看原问题的常规解法,其实是一个不算复杂的动态规划。假设str1的长度为M,str2的长度为N,我们使用一张大小为(M+1)*(N+1)的矩阵结构的动态规划表dpMap,dpMap[i][j]的值代表str1[0..i-1]变到str2[0..j-1]的最小代价,现在用举例的方式来具体说明dpMap是如何计算:
例子:
String str1 = "ab12cd3";
String str2 = "abcdf";
a = 5;
b = 3;
c = 2;
str1的长度为7,str2的长度为5,所以dpMap是一张8*6的矩阵,计算结果如下:
'' 'a' 'b' 'c' 'd' 'f'
例如:
Str1="ac";
Str2="abc";
a = 5
b = 3
c = 2
最好的转化路径为在Str1中的a和c中间直接插入一个b即可完成转化,所以最小代价为5。
Str1="ab";
Str2="bb";
a = 5
b = 4
c = 3
最好的转化路径为将Str1中的a直接替换成b即可完成转化,所以最小代价为3。
进阶:如果Str1的长度为M,Str2的长度为N,你的代码需优化到在时间复杂度不低于O(M*N)的情况下,额外空间复杂度为O(Min{M,N})
解答:
难度:尉
进阶难度:校
先看原问题的常规解法,其实是一个不算复杂的动态规划。假设str1的长度为M,str2的长度为N,我们使用一张大小为(M+1)*(N+1)的矩阵结构的动态规划表dpMap,dpMap[i][j]的值代表str1[0..i-1]变到str2[0..j-1]的最小代价,现在用举例的方式来具体说明dpMap是如何计算:
例子:
String str1 = "ab12cd3";
String str2 = "abcdf";
a = 5;
b = 3;
c = 2;
str1的长度为7,str2的长度为5,所以dpMap是一张8*6的矩阵,计算结果如下:
'' 'a' 'b' 'c' 'd' 'f'
'' 0 5 10 15 20 25
'a' 3 0 5 10 15 20
'b' 6 3 0 5 10 15
'1' 9 6 3 2 7 12
'2' 12 9 6 5 4 9
'c' 15 12 9 6 7 6
'd' 18 15 12 9 6 9
'3' 21 18 15 12 9 8
怎么得到的呢?先来说明矩阵中第0行所有的值(dpMap[0][j
])是如何得到的,根据dpMap的定义,dpMap[0][j
]的含义是当str1一个字符也没有的情况下(也就是""),从""变到str2[0..j
-1]的最小代价。
dpMap[0][0]代表从""变到""的最小代价,无疑是0;
dpMap[0][1]代表从""变到"a"的最小代价,无疑是插入1个字符('a')的代价5;
dpMap[0][2]代表从""变到"ab"的最小代价,无疑是插入2个字符('a','b
')的代价10;
dpMap[0][3]代表从""变到"abc"的最小代价,无疑是插入3个字符('a','b
','c')的代价15;
...
dpMap[0][j]代表从""变到str2[0..j-1]的最小代价,无疑是插入j个字符的代价5*j;
然后来说明矩阵中第0列所有的值(dpMap[i][0
])是如何得到的,根据dpMap的定义,dpMap[i][0
]的含义是str1[0..i-1]变到str2一个字符也没有的情况下(也就是"")的最小代价。
dpMap[0][0]代表从""变到""的最小代价,无疑是0;
dpMap[1][0]代表从"a"变到""的最小代价,无疑是删除1个字符('a')的代价3;
dpMap[2][0]代表从"ab"变到""的最小代价,无疑是删除2个字符('a','b
'a' 3 0 5 10 15 20
'b' 6 3 0 5 10 15
'1' 9 6 3 2 7 12
'2' 12 9 6 5 4 9
'c' 15 12 9 6 7 6
'd' 18 15 12 9 6 9
'3' 21 18 15 12 9 8
怎么得到的呢?先来说明矩阵中第0行所有的值(dpMap[0][j
])是如何得到的,根据dpMap的定义,dpMap[0][j
]的含义是当str1一个字符也没有的情况下(也就是""),从""变到str2[0..j
-1]的最小代价。
dpMap[0][0]代表从""变到""的最小代价,无疑是0;
dpMap[0][1]代表从""变到"a"的最小代价,无疑是插入1个字符('a')的代价5;
dpMap[0][2]代表从""变到"ab"的最小代价,无疑是插入2个字符('a','b
')的代价10;
dpMap[0][3]代表从""变到"abc"的最小代价,无疑是插入3个字符('a','b
','c')的代价15;
...
dpMap[0][j]代表从""变到str2[0..j-1]的最小代价,无疑是插入j个字符的代价5*j;
然后来说明矩阵中第0列所有的值(dpMap[i][0
])是如何得到的,根据dpMap的定义,dpMap[i][0
]的含义是str1[0..i-1]变到str2一个字符也没有的情况下(也就是"")的最小代价。
dpMap[0][0]代表从""变到""的最小代价,无疑是0;
dpMap[1][0]代表从"a"变到""的最小代价,无疑是删除1个字符('a')的代价3;
dpMap[2][0]代表从"ab"变到""的最小代价,无疑是删除2个字符('a','b
剩余5页未读,继续阅读
资源评论
crazyfish1986
- 粉丝: 1
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功