Compute edit distance when insertions, deletions and substitutions have different costs.
What to build
A program that computes weighted edit distances with dynamic programming.
Requirements
- Line 1 gives the costs of an insertion, a deletion and a substitution. Turning a into b, a deletion removes a character of a and an insertion adds a character of b; matching characters cost 0.
- For each pair print
a -> b: D, the minimum total cost.
Input
Line 1: three integer costs. Line 2: n. Then n lines with two words.
Output
n lines.
Constraints
Costs from 1 to 10; words have at most 100 characters.
Example
Input:
1 1 1
2
kitten sitting
flaw lawn
Output:
kitten -> sitting: 3
flaw -> lawn: 2
Why it works
The cheapest way to turn a prefix of a into a prefix of b must end with a deletion, an insertion or a substitution (or a free match), so each cell is the best of those three options built on smaller prefixes.
Examples
1 1 1 2 kitten sitting flaw lawn
kitten -> sitting: 3 flaw -> lawn: 2
1 1 2 2 intention execution cat cut
intention -> execution: 8 cat -> cut: 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The first row is `[j * ins for j in range(len(b) + 1)]` and each new row starts with `i * dele`.
Hint 2
Each cell is the minimum of the cell above + delete, the cell to the left + insert, and the diagonal + (0 or the substitution cost).
Solution
Show one correct solution (try it yourself first)
ins, dele, sub = map(int, input().split())
for _ in range(int(input())):
a, b = input().split()
prev = [j * ins for j in range(len(b) + 1)]
for i in range(1, len(a) + 1):
cur = [i * dele]
for j in range(1, len(b) + 1):
cost = 0 if a[i - 1] == b[j - 1] else sub
cur.append(min(prev[j] + dele, cur[j - 1] + ins, prev[j - 1] + cost))
prev = cur
print(f"{a} -> {b}: {prev[-1]}")