You want to fix a wrongly typed caption string A into the correct string B.
There are three kinds of edits, and each one costs something every time it is done.
Insert: put one character anywhere. It costs I.
Delete: erase one character. It costs D.
Replace: change one character into a different character. It costs R.
Using the three edits any number of times in any order to make A exactly equal to B, print the smallest possible total cost.
If A and B are already equal, print 0.
Input
The first line has I, D, R separated by spaces. The second line has A and the third line has B. A and B consist of lowercase English letters only. 1 ≤ I, D, R ≤ 1,000, 1 ≤ length of A and of B ≤ 1,000
Output
The smallest total cost
Example 1 · stdin
1 1 5
abcd
abxd
stdout
2
Example 2 · stdin
3 2 4
banana
bandana
stdout
3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This is dynamic programming with a table dp[i][j] = 'the smallest cost to turn the first i characters of A into the first j characters of B'. Looking at the last characters there are only three ways: keep them if equal (dp[i-1][j-1]) or replace if not (dp[i-1][j-1] + R), delete the i-th character of A (dp[i-1][j] + D), or insert the j-th character of B (dp[i][j-1] + I), taking the smallest. When R is large, as in the first example, deleting and inserting (1 + 1 = 2) is cheaper than replacing — taking the minimum handles it by itself. A cell only looks at the row above and the current row, so two rows are enough (two rows of 1,001 instead of a 1,001 × 1,001 table). Trap one: swapping insert and delete is wrong when I ≠ D — writing a character of B (the side where j drops by one) is the insert. Trap two: the first row and column are j * I (insert everything into an empty string) and i * D (delete everything), not the character counts — thinking of the usual edit distance with cost 1 and writing j, i is wrong. Trap three: overwriting a single row means row[j-1] already holds this row's value, so the upper-left (diagonal) value is lost — use two rows or save the diagonal separately. Swapping the two rows differs by language: C swaps two pointers, C++ std::swap(prev, cur) swaps only the vectors' insides with no copying, Java swaps array references, and C# uses the tuple (prev, cur) = (cur, prev). Python, JavaScript, TypeScript and Craykon make a new list for each row and hand it on with prev = cur (Craykon NewList(b.Length + 1, 0)). Reading characters differs too: Python, JavaScript, TypeScript and C# use a[i - 1], Java a.charAt(i - 1), C reads into an array with a width as in scanf("%1001s", a), and in Craykon the string read with Console.ReadLine().Trim() gives a one-character string for a[i - 1], compared with ==. The cost is at most 1,000 × 1,000 × 2 = 2 million, so int is enough in every language.
Pythonmain.py · 16 lines
import syslines = sys.stdin.read().split()ins, dele, rep = int(lines[0]), int(lines[1]), int(lines[2])a, b = lines[3], lines[4]# prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [j * ins for j in range(len(b) + 1)] # 빈 문자열에서 b의 앞 j글자: 모두 넣기for i in range(1, len(a) + 1): cur = [i * dele] + [0] * len(b) # a의 앞 i글자에서 빈 문자열: 모두 빼기 for j in range(1, len(b) + 1): keep = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else rep) # 그대로 두거나 바꾸기 cur[j] = min(keep, prev[j] + dele, cur[j - 1] + ins) # a[i-1] 빼기, b[j-1] 넣기 prev = curprint(prev[len(b)])
JavaScriptmain.js · 15 lines
const [ins, del, rep, a, b] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep);// prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur = new Array(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);
TypeScriptmain.ts · 17 lines
import { readFileSync } from "node:fs";const [ins, del, rep, a, b] = readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep);// prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev: number[] = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur: number[] = new Array<number>(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);
JavaMain.java · 32 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int ins = Integer.parseInt(st.nextToken()); int del = Integer.parseInt(st.nextToken()); int rep = Integer.parseInt(st.nextToken()); String a = in.readLine().trim(); String b = in.readLine().trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) int[] prev = new int[b.length() + 1]; int[] cur = new int[b.length() + 1]; for (int j = 0; j <= b.length(); j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.length(); i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.length(); j++) { int keep = prev[j - 1] + (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, Math.min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } int[] t = prev; // 두 줄을 맞바꾼다(새로 만들지 않는다) prev = cur; cur = t; } System.out.println(prev[b.length()]); }}
C#Main.cs · 28 lines
using System;class Program{ static void Main() { string[] c = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int ins = int.Parse(c[0]), del = int.Parse(c[1]), rep = int.Parse(c[2]); string a = Console.ReadLine().Trim(); string b = Console.ReadLine().Trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) var prev = new int[b.Length + 1]; var cur = new int[b.Length + 1]; for (int j = 0; j <= b.Length; j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.Length; i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.Length; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.Min(keep, Math.Min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } (prev, cur) = (cur, prev); // 두 줄을 맞바꾼다(새로 만들지 않는다) } Console.WriteLine(prev[b.Length]); }}
C++main.cpp · 23 lines
#include <algorithm>#include <iostream>#include <string>#include <vector>int main() { int ins, del, rep; std::string a, b; std::cin >> ins >> del >> rep >> a >> b; // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) std::vector<int> prev(b.size() + 1), cur(b.size() + 1); for (size_t j = 0; j <= b.size(); j++) prev[j] = static_cast<int>(j) * ins; // 빈 문자열에서: 모두 넣기 for (size_t i = 1; i <= a.size(); i++) { cur[0] = static_cast<int>(i) * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (size_t j = 1; j <= b.size(); j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = std::min({keep, prev[j] + del, cur[j - 1] + ins}); // 빼기, 넣기 } std::swap(prev, cur); // 벡터 속만 맞바꾼다(복사하지 않는다) } std::cout << prev[b.size()] << "\n";}
Cmain.c · 36 lines
#include <stdio.h>#include <string.h>#define MAXL 1000static char a[MAXL + 2], b[MAXL + 2];static int row0[MAXL + 1], row1[MAXL + 1];static int min3(int x, int y, int z) { int m = x < y ? x : y; return m < z ? m : z;}int main(void) { int ins, del, rep; scanf("%d %d %d", &ins, &del, &rep); scanf("%1001s %1001s", a, b); int n = (int)strlen(a), m = (int)strlen(b); /* prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) */ int* prev = row0; int* cur = row1; for (int j = 0; j <= m; j++) prev[j] = j * ins; /* 빈 문자열에서: 모두 넣기 */ for (int i = 1; i <= n; i++) { cur[0] = i * del; /* a의 앞 i글자에서 빈 문자열: 모두 빼기 */ for (int j = 1; j <= m; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); /* 그대로 두거나 바꾸기 */ cur[j] = min3(keep, prev[j] + del, cur[j - 1] + ins); /* 빼기, 넣기 */ } int* t = prev; /* 포인터만 맞바꾼다 */ prev = cur; cur = t; } printf("%d\n", prev[m]); return 0;}
Craykonmain.cray · 29 lines
비용 = Console.ReadNumbers();ins = 비용[0];del = 비용[1];rep = 비용[2];a = Console.ReadLine().Trim();b = Console.ReadLine().Trim();// prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [];for (j = 0; j <= b.Length; j++){ prev.Add(j * ins); // 빈 문자열에서 b의 앞 j글자: 모두 넣기}for (i = 1; i <= a.Length; i++){ cur = NewList(b.Length + 1, 0); cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (j = 1; j <= b.Length; j++) { keep = prev[j - 1] + rep; // 다른 글자로 바꾸기 if (a[i - 1] == b[j - 1]) { keep = prev[j - 1]; // 같은 글자는 그대로 둔다 } cur[j] = Mathf.Min(keep, Mathf.Min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } prev = cur;}Console.WriteLine(prev[b.Length]);