解題區►Uva

Uva 526 - String Distance and Transform Process

題目

Problem

字串距離是一個代表兩個字串的非負整數。接著要轉換(transform)$a$字串至$b$字串，有三種操作：插入(Insert)、刪除(Delete)、及取代（Replace)。
字串距離就是轉換的數量，求任意$a$字串轉換至$b$字串的字串距離及如何轉換的。

輸入

每筆case有兩行字串$a$、$b$，以EOF結尾，字串的長度不超過$80$

輸出

每筆輸出第一行為一個整數($n$)，代表字串距離(String distance)。
接著有有$n$行，每行為一個操作指令，格式如下：

  • Insert pos,value
  • Delete pos
  • Replace pos,value

sample input

1
2
3
4
abcac
bcd
aaa
aabaaaa

sample output

1
2
3
4
5
6
7
8
9
10
3
1 Delete 1
2 Replace 3,d
3 Delete 4

4
1 Insert 1,a
2 Insert 2,a
3 Insert 3,b
4 Insert 7,a

想法

dp[i][j]代表從a[1..i]到b[1..i]的最小字串距離。
a[i], b[i]都是1-index

  • 紅色箭頭：當a[i] != b[j]時

    • 從上方、左方、左上方挑一個最小的，然後字串距離+1
      • 往下:刪除a[i]字元
      • 往右：插入b[j]字元
      • 往由下：把a[i]字元取代成b[j]字元

  • 藍色箭頭：當a[i] == b[j]時

    • 不用做變換，所以字串距離一樣。

  • 範例

    1
    2
    3
    4
    5
    6
    7
    8
      j 0 1 2 3
    i +--------
    0 | 0 1 2 3
    1 | 1 1 2 3
    2 | 2 1 2 3
    3 | 3 2 1 2
    4 | 4 3 2 2
    5 | 5 4 3 3
    • dp[5][3] 及為$a$到$b$的最小字串距離

  • 最後輸出由右下backtracking回去即可

AC Code

https://github.com/roy4801/solved_problems/blob/master/uva/526.cpp

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

推薦文章