UVa 1207 - AGTC - Willy's Blog

題目簡述

輸入兩個字串 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 ，可以思考一下原因

程式碼

/*****************************************
  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 ;
}