805 . 編輯距離

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

80.0% (4/5)

Tags

apcsc apcsc-dp

Description

兩個字串之間的編輯距離被定義為：經由以下三種操作，將兩字串變成相同字串所需的最少操作次數

  • 選擇一個字串並在不改變順序下插入一個字元。
  • 選擇一個字串並刪除一個字元
  • 選擇一個字串的某個字元，並把他修改成另一個字元。

給你兩個字串 $s, t$，試求其編輯距離。

Input Format

輸入有兩行，第一行是字串 $s$，第二行是字串 $t$。

輸入保證 $1\le |s|, |t| \le 2000$，且輸入的字元僅包含小寫英文字母。

Output Format

輸出一行一個整數，代表 $s,t$ 的編輯距離。

Sample Input 1

abc
acd

Sample Output 1

2

Sample Input 2

false
ifelse

Sample Output 2

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~17 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
Submit
Back to Top