0%

字符串比较问题

【问题描述】对于长度相同的两个字符串A和B,其距离定义为相应位置字符距离之和。两个非空格字符的距离是它们的ASCII编码之差的绝对值。空格与空格的距离为0, 空格与其他字符的距离为一定值k。在一般情况下,字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离。对于给定的字符串A和B, 试设计一个算法,计算其扩展距离。

【算法设计】对于给定的字符串A和B,计算其扩展距离。

【输入形式】第一行是字符串A,第二行是字符串B,第三行是空格与其他字符的距离定值k 。

【输出形式】输出计算出的字符串A和B的扩展距离。

典型的动态规划问题,设 $dp[len(A)][len(B)]$ 代表 A 和 B 的扩展距离。
可以得到:

$$
dp[i][j] = min(dp[i-1][j-1]+abs(A[i]-B[j]),dp[i-1][j]+k, dp[i][j-1]+k)​
$$

解释一下就是:

  • 当$A[i]$和$B[j]$都不是第一个字符时,结果可以取$A[0:i-1]$和$B[0:j-1]$的扩展距离加 $A[i]$和$B[j]$的扩展距离。
  • 当$A[i]$不是第一个字符时,结果可以取$A[0:i-1]$和$B[0:j]$的扩展距离加$A[i]$与在$B$末尾中添加的一个空格的扩展距离。
  • 当$B[i]$不是第一个字符时,结果可以取$A[0:i]$和$B[0:j-1]$的扩展距离加$B[i]$与在$A$末尾中添加的一个空格的扩展距离。
  • 结果就是上面三个的最小值。(还需要注意一下边界)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e3+10;
const int INF = INT_MAX;
int dp[maxn][maxn], k, lena, lenb;
char a[maxn], b[maxn];
int dist(char i, char j){
if(i==' ' && j==' ') return 0;
if(i==' ' || j==' ') return k;
return abs(i-j);
}
int main(){
while(scanf("%s%s%d", a, b, &k)!=EOF){
lena = strlen(a); lenb = strlen(b);
for(int i=0; i<=lena; i++){
for(int j=0; j<=lenb; j++){
if(i+j) dp[i][j] = INF;
if(i*j) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + dist(a[i-1], b[j-1]));
if(i) dp[i][j] = min(dp[i][j], dp[i-1][j] + dist(a[i-1], ' '));
if(j) dp[i][j] = min(dp[i][j], dp[i][j-1] + dist(b[j-1], ' '));
}
}
printf("%d", dp[lena][lenb]);
}

return 0;
}