a145. 最短編輯距離 - 旦旦解題農場

內容

最小編輯距離(edit distance)是針對二個字符串的差異程度的量化量測，量測方式是看至少需要多少次的處理(新增一個字元、刪除一個字元、修改一個字元都算一次操作)才能將一個字符串變成另一個字符串。現在給你兩字串 S, T，問你從字串S修改成字串T的最小編輯距離是多少?

輸入說明

多筆測資讀到EOF為止(不超過5筆)。

每筆測資包含兩行兩個字串$S,T$。

20%測資符合$1\le |S|,|T|\le 10$

所有測資符合$1\le |S|,|T|\le 1000$，且字串接只包含小寫因為字母。

輸出說明

每筆測資輸出一個數字代表將$S$修改成$T$的最小編輯距離。

範例輸入

ababc
acac
aabc
abcb

範例輸出

2
2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

以下為範測其中一種最短修改的方法：

ababc->acabc->acac

aabc->abc->abcb

標籤:

出處:

暑期培訓小考(四) [管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」