題目簡述

  • 輸入兩個字串 x 和 y ,要把字串 x 轉換成字串 y

  • 可以進行的操作步驟是

    1. 刪除一個字母
    2. 插入一個字母
    3. 置換一個字母
  • 輸出最少的操作步驟把字串 x 轉換成字串 y

    解題想法

  • 這題主要就是建立一個二維陣列,然後想要如何填這個陣列

  • 若我們定義 $C_{i, j}$ 是從字串 $a_i$ 到 $b_j$ 的最小操作數量,則 $C_{i, j}$ 的規則如下
    $$C_{i, j}=min
    \begin{cases}
    C_{i-1, j}+1&&刪除a_j\\
    C_{i, j-1}+1&&插入b_j\\
    C_{i-1, j-1}+d_{i, j}&&置換\\
    \end{cases}$$
    $$d_{i, j}=
    \begin{cases}
    0&&if\ \ a_i=b_j\\
    1&&if\ \ a_i\neq b_j\\
    \end{cases}$$

  • 例如字串 A 為 “abbc”, 字串 B 為 “babb”,最後陣列會是這個樣子

    • 以上面框起來的那格 $C_{2,2}$ 來說,這格可以從…
      • 左方($C_{2,1}$)過來(插入):A字串插入 $b_2$
      • 上方($C_{1,2}$)過來(刪除):A字串刪除 $a_2$
      • 左上方($C_{1,1}$)過來(置換):A字串置換 $a_2$ 成 $b_2$
        • 注意置換的 $d_{i, j}$ ,若是 $a_2$ 等於 $b_2$ ,那其實就不用置換了(因為兩個字母相同),若是不相等,那就需要進行置換的動作
      • 然後找最小值,所以數值為 2
    • 所以把整個陣列填完後,最後最小的路徑為以下這樣,最小操作步驟為 2 步
  • 最後補充一下,初始化的數值是陣列 $ a_0 $ 和 $ b_0 $ 的那一行/列 ,其數值是從 0 開始依序往上加 1 ,可以思考一下原因

程式碼

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
33
34
35
36
37
38
39
40
41
42
43
44
45
/*****************************************
Filename:p1207.cpp
Author:Willy Chen(willychen.org)
Date:2019.09.22
*****************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

/* Find the minimum value */
int find_min(int a, int b, int c){
int ans = a;
if(b < ans)
ans = b;
if(c < ans)
ans = c;
return ans;
}

int main(){
char s1[1000], s2[1000];
int num1, num2;
while(scanf("%d%s", &num1, &s1[1]) != EOF){
scanf("%d%s", &num2, &s2[1]);
int graph[1000][1000]={0};

/* Initialize the graph */
for(int i = 0; i < 1000; ++i){
graph[0][i]=i;
graph[i][0]=i;
}
for(int i = 1; i <= num1; ++i){
for(int j = 1; j <= num2; ++j){
/* Replace operation */
int num_re = graph[i-1][j-1];
if(s1[i] != s2[j]) num_re++;
/* Find the minimum number of operations */
graph[i][j] = find_min(num_re, graph[i-1][j]+1, graph[i][j-1]+1);
}
}
cout << graph[num1][num2] << endl;
}
return 0 ;
}

評論

 無法加載Disqus評論系統,請確保您的網絡能夠正常訪問。



本站使用 Volantis 作為主題