[题解]hihoCoder挑战赛18——题目1 神奇字符串
题目地址：http://hihocoder.com/problemset/problem/1264
描述
我们说两个字符串是非常相似的,当且仅当它们的编辑距离小于等于1.
现在我们有两个字符串A和B, 每个单位时间你可以交换字符串A的相邻的两个字符.
问最少需要多少时间,你可以让A和B变得非常相似?保证存在一种这样的方案.
输入
第一行一个字符串,表示A.
第二行一个字符串,表示B.
所有字符串都仅有英文小写字母组成.
A和B的长度都不超过100.
输出
一行表示最少需要的时间.
样例输入
nwlrb
rclwnb
样例输出
6
解题思路
首先要搞清楚什么叫“编辑距离”。编辑距离（Edit Distance）是指两个字串之间，由一个字串变成另一个字串所需要的最少编辑操作次数。编辑操作包括三种：将一个字符替换为另一个字符、插入一个字符、删除一个字符。
由题目要求知道，这样方案一定存在，那么A、B两个字串要么长度相同，要么长度相差1。分类讨论，设n为A串的长度，m为B串的长度，A串最后变成C串，C串与B串的编辑距离<=1。
当n==m时，这时C串长度与A、B串一样，所以与B串要么一样，要么有一个字母不一样；当n==(m+1)时，表示C串要添加一个字符得到B串，同样也是B串删除一个字符得到C串；当(n+1)==m时，表示C串要删除一个字符得到B串，同样B串添加一个字符也可以得到C串。
现在再考虑A串怎么变成C串的。题目给出的对A串的操作只有交换两个相邻的字符，由优化思想可以知道，如果两个相邻的字符是相同的，则没有必要交换，所以说相同的字符之间的相对顺序是不会改变的，于是当C串固定时，A串变为C串的一一对应关系是确定的，也就是说A串中第k个字母a一定变到C串种第k个字母a的位置上。这样问题就转换为求逆序对数量的问题了。
思路比较清楚了，如何实现呢？我们可以枚举与B串编辑距离<=1的C串，第一种情况时间复杂度为O(n)，后两种情况时间复杂度为O(n^2)。（后两种似乎可以用链表的形式优化为O(n)，时间限制不苛刻，这里没有过多考虑）再计算A串到C串的交换次数，即逆序对的数量，时间复杂度为O(n^2)。
附：C++代码
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <algorithm>
5 #include <cstring>
6
7 using namespace std;
8 #define MaxN 120
9 #define INF 1e9
10
11 int n, m, Last[MaxN];
12 char A[MaxN], B[MaxN], C[MaxN];
13
14 vector <int> Pos[30];
15
16 int Dis()
17 {
18 int i, j, x;
19 for(i = 0; i < 26; i++)
20 Pos[i].clear();
21 for(i = n; i > 0; i--)
22 Pos[C[i] - 'a'].push_back(i);
23 for(i = 1; i <= n; i++)
24 {
25 x = A[i] - 'a';
26 if(Pos[x].size() == 0)
27 return INF;
28 else
29 {
30 Last[i] = Pos[x][Pos[x].size() - 1];
31 Pos[x].pop_back();
32 }
33 }
34 int Ans = 0;
35 for(i = 1; i <= n; i++)
36 for(j = i + 1; j <= n; j++)
37 if(Last[i] > Last[j])
38 Ans++;
39 return Ans;
40 }
41
42 int main()
43 {
44 int i, j, Ans = INF;
45 scanf("%s", A + 1);
46 scanf("%s", B + 1);
47 n = strlen(A + 1);
48 m = strlen(B + 1);
49 if(n == m)
50 {
51 memcpy(C, B, sizeof(B));
52 for(i = 1; i <= n; i++)
53 {
54 for(j = 0; j < 26; j++)
55 {
56 C[i] = 'a' + j;
57 Ans = min(Ans, Dis());
58 }
59 C[i] = B[i];
60 }
61 }
62 else if(n == (m + 1))
63 {
64 for(i = 0; i <= m; i++)
65 {
66 for(j = 1; j <= i; j++)
67 C[j] = B[j];
68 for(j = i + 1; j <= m; j++)
69 C[j + 1] = B[j];
70 for(j = 0; j < 26; j++)
71 {
72 C[i + 1] = 'a' + j;
73 Ans = min(Ans, Dis());
74 }
75 }
76 }
77 else
78 {
79 for(i = 1; i <= m; i++)
80 {
81 for(j = 1; j < i; j++)
82 C[j] = B[j];
83 for(j = i + 1; j <= m; j++)
84 C[j - 1] = B[j];
85 Ans = min(Ans, Dis());
86 }
87 }
88 printf("%d", Ans);
89 return 0;
90 }
最新文章
- 浅谈JavaScript、ES5、ES6
- var a=function()跟function a()的区别
- Mac 配置 vim
- vs2010调试程序出现“Cannot find or open the PDB file”
- 这是一个比较清晰的SSH框架结构，有兴趣的博友可以看一下
- Apache Storm 的历史及经验教训——Nathan Marz【翻译】
- SpringMVC Controller 返回值的可选类型
- Linux安装telnet
- 游戏服务器端引擎--DogSE的设计
- 正确的SVN导入代码命令
- Django框架学习-Model进阶用法
- poj3292-类素数筛选法
- 一起来看看css中的单位
- KNN算法理解
- 在Eclipse中用TODO标签管理任务(Task)
- UVa1630,Folding
- defaultdict使用及__missing__理解
- ●BZOJ 4559 [JLoi2016]成绩比较(容斥)
- mac pro 基本使用
- JVM调优命令-jstack