/ rignts / 题库 /

字符串修改

字符串修改

问题描述:

给定两个字符串s1、s2,李华想在操作次数最少的前提下用尽可能少的代价将s1变成s2。
对字符串的操作有三种:
1. 将一个字符改为另一个字符,操作的代价为1;
2. 删除一个字符,操作的代价为2;
3. 插入一个字符,操作的代价为3;
对任给的两个字符串A和B,计算出将字符串A变换为字符串B的操作次数,并输出每次操作后的字符串。

输入:

第一行输入字符串s1
第二行输入字符串s2

输出:

第一行输出最少的操作次数n
接下来n行输出每次操作之后的字符串

Input

emdsic
efxaasi

Output

5
1:efmdsic
2:efxmdsic
3:efxadsic
4:efxaasic
5:efxaasi

数据范围:

对于50%的数据:s1、s2的长度<=10
对于60%的数据:s1、s2的长度<=100
对于80%的数据:s1、s2的长度<=500
对于100%的数据:s1、s2的长度<=1000

Hint

开始时字符串为:emdsic
第1次操作:在第一和第二个字母之间插入一个f,字符串变为:efmdsic
第2次操作:在第二和第三个字母之间插入一个x,字符串变为:efxmdsic
第3次操作:将第四个字母变为a,字符串变为:efxadsic
第4次操作:将第五个字母变为a,字符串变为:efxaasic
第5次操作:将第八个字母删除,字符串变为:efxaasi

Limitation

1s, 64M for each test case.

信息

ID
1013
难度
9
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
上传者