Cheapest Rewrite With Priced Edits
Medium2-D Dynamic Programming
Problem
A typesetting machine rewrites a word source into target one character at a time. Inserting a character costs insertCost, deleting one costs deleteCost, and replacing one character with a different one costs replaceCost. Keeping a character unchanged is free.
Return the minimum total cost to turn source into target.
Example 1
- Input:
- source = "cart", target = "chart", insertCost = 2, deleteCost = 3, replaceCost = 4
- Output:
- 2
Insert "h" after "c".
Example 2
- Input:
- source = "paper", target = "pepper", insertCost = 1, deleteCost = 1, replaceCost = 5
- Output:
- 3
Replacing "a" with "e" would cost 5; deleting "a" and inserting "e" costs 2, plus 1 to insert the extra "p".
Example 3
- Input:
- source = "abc", target = "xyz", insertCost = 1, deleteCost = 1, replaceCost = 10
- Output:
- 6
Delete all three letters and insert three new ones.
Constraints
- 0 ≤ source.length, target.length ≤ 500
- 1 ≤ insertCost, deleteCost, replaceCost ≤ 100
- Both strings contain lowercase English letters only.
Hint
Show the first hint
This is edit distance where the three operations no longer cost the same. Does the prefix-pair state still work?
Walkthrough
How to approach it
01Clarify before coding
- Is a replace with the same character free? Yes, that is a keep.
- Can a replace cost more than a delete plus an insert? Yes, and then the DP simply never uses it.
- Are costs per character, not per operation length? Yes, each character inserted or deleted is charged separately.
02Brute force
Recursively align the first characters, branching into keep/replace, delete and insert, and take the cheapest.
Cost: O(3^(m + n)) without memoisation.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.