Show problems as
Classic problem #3995HardArrayStringDynamic Programming

Minimum Cost to Convert String III

Real-world version: Rewriting a Tape With Patterned Rules
Tracked in this browser only
Read Minimum Cost to Convert String III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two tapes of equal length are given as source and target.

Each entry of rules is a pair [pattern, replacement] of equal length, and costs[i] is what that rule charges. A '*' in a pattern stands for any single letter; a replacement holds letters only.

Choose any number of stretches of source that do not overlap each other. Each chosen stretch is rewritten by one rule whose pattern matches that stretch of source and whose replacement is exactly the matching stretch of target, at that rule's cost. Every position left uncovered must already read the same on both tapes.

Return the least total cost of turning source into target, or -1 when it cannot be done.

Examples

Example 1

Input
source = "aa", target = "bb", rules = [["a", "b"], ["aa", "bb"]], costs = [2, 3]
Output
3

Rewriting each letter on its own costs 2 twice, coming to 4, while the rule covering both letters at once costs 3, so the wider rule wins.

Example 2

Input
source = "a", target = "b", rules = [["a", "c"]], costs = [3]
Output
-1

The only rule turns the letter into c, which is not what the target reads, so nothing can be done.

Example 3

Input
source = "abc", target = "abc", rules = [["*", "z"]], costs = [1]
Output
0

The two tapes already read the same everywhere, so every position may be left alone and nothing needs paying for.

Constraints

  • 1 <= source.length <= 5000
  • source.length == target.length
  • source and target consist of lowercase English letters only
  • 1 <= rules.length <= 200
  • rules.length == costs.length
  • rules[i].length == 2
  • 1 <= rules[i][0].length <= 20
  • rules[i][0].length == rules[i][1].length
  • rules[i][0] holds lowercase letters and at most 5 '*' characters
  • rules[i][1] holds lowercase letters only
  • 1 <= costs[i] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_cost(source: str, target: str, rules: list[list[str]], costs: list[int]) -> int:
Java
public int minCost(String source, String target, List<List<String>> rules, int[] costs)

More on the same topics