0941HardArrayStringDynamic Programming

Rewriting a Tape With Patterned Rules

Tracked in this browser only

Trains the technique from

LeetCode 3995Minimum Cost to Convert String III

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n * r * L) for a tape of length n, r rules of length at most L.Space O(n) for the running costs.

The chosen stretches never overlap, so reading the tapes left to right the decisions are independent once a position is passed: either the position is left alone, which is allowed only when the two tapes already agree there, or it opens a stretch that some rule covers and the reading resumes just past that stretch. That makes it one sweep holding, for each position, the least cost of settling everything before it. Moving on by one costs nothing when the tapes agree. Applying a rule at a position costs that rule, and the rule fits when its pattern matches `source` there, with a `'*'` accepting whatever letter sits under it, and its replacement matches `target` there exactly. Rules are short, so checking a fit is cheap, and unreachable positions stay unreachable. An unreachable end means the tapes cannot be brought together at all.

Pythonentry point: min_cost

def min_cost(source, target, rules, costs):
    n = len(source)
    INF = float("inf")
    best = [INF] * (n + 1)
    best[0] = 0
    for i in range(n):
        if best[i] == INF:
            continue
        if source[i] == target[i] and best[i] < best[i + 1]:
            best[i + 1] = best[i]
        for r in range(len(rules)):
            pattern = rules[r][0]
            replacement = rules[r][1]
            length = len(pattern)
            if i + length > n:
                continue
            fits = True
            for at in range(length):
                want = pattern[at]
                if want != "*" and want != source[i + at]:
                    fits = False
                    break
                if replacement[at] != target[i + at]:
                    fits = False
                    break
            if not fits:
                continue
            here = best[i] + costs[r]
            if here < best[i + length]:
                best[i + length] = here
    if best[n] == INF:
        return -1
    return best[n]

The obvious version

Search the positions outright: from a position, either step over it when the tapes already agree or try every rule that fits and carry on past it, keeping the cheapest finish found. Remembers nothing between branches, so the same position is settled again and again.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost(source, target, rules, costs):
    n = len(source)

    def walk(at):
        if at == n:
            return 0
        best = None
        if source[at] == target[at]:
            rest = walk(at + 1)
            if rest is not None:
                best = rest
        for r in range(len(rules)):
            pattern = rules[r][0]
            replacement = rules[r][1]
            length = len(pattern)
            if at + length > n:
                continue
            fits = True
            for k in range(length):
                if pattern[k] != "*" and pattern[k] != source[at + k]:
                    fits = False
                    break
                if replacement[k] != target[at + k]:
                    fits = False
                    break
            if not fits:
                continue
            rest = walk(at + length)
            if rest is None:
                continue
            here = rest + costs[r]
            if best is None or here < best:
                best = here
        return best

    answer = walk(0)
    if answer is None:
        return -1
    return answer

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in