Minimum Cost of Nonoverlapping String Replacements

# Minimum Cost of Nonoverlapping String Replacements You are given equal-length lowercase strings `source` and `target`, an array `rules`, and an equally sized integer array `costs`. Each `rules[i]` contains a pattern and a replacement string of the same length. A pattern contains lowercase letters and possibly `'*'` characters. Each `'*'` matches exactly one character. Replacements contain only lowercase letters and are used literally. To apply a rule, choose a range of the current string having the rule's length. Every pattern letter must match the corresponding current character; a wildcard matches any character. Replace the range with the rule's replacement. The application costs its base `costs[i]` plus the number of wildcards in its pattern. Every position in that range becomes used. A later application cannot touch any used position, even if its character did not change. All replacements preserve string length. You may reuse a rule on different, disjoint ranges. Return the minimum total cost to obtain `target`, or `-1` if it is impossible. ### Function `int minCost(string source, string target, vector<vector<string>>& rules, vector<int>& costs)` ### Example 1 **Input:** `source = "abca", target = "xyaa", rules = [["a*", "xy"], ["c", "a"], ["abc", "xyz"]], costs = [4, 2, 1]` **Output:** `7` **Explanation:** Apply the first rule to positions `0..1`, paying `4 + 1 = 5` because its pattern has one wildcard. The string becomes `"xyca"`. Apply the second rule to position `2` for cost `2`, obtaining `"xyaa"`; the last character is left unchanged. Total cost is `7`. The cheaper third rule would leave `"xyz"` at already-used positions `0..2`, so its `z` could not later be corrected. ### Example 2 **Input:** `source = "a", target = "c", rules = [["a", "b"], ["b", "c"]], costs = [1, 1]` **Output:** `-1` **Explanation:** Changing `"a"` to `"b"` uses its only position. Applying another rule there is then forbidden, so the apparent two-step conversion to `"c"` is not legal. ### Constraints - `1 <= source.length == target.length <= 5000` - `source` and `target` contain only lowercase English letters. - `1 <= rules.length == costs.length <= 200` - Every rule contains exactly `[pattern, replacement]`. - `1 <= pattern.length == replacement.length <= 20` - Every pattern contains at least one lowercase English letter and at most five `'*'` characters. - Every replacement contains only lowercase English letters. - `1 <= costs[i] <= 1000` ### Clarifications - A wildcard consumes one position, not an arbitrary-length substring. - Applied ranges may be adjacent, but they cannot overlap or be used again. - Positions not included in any application retain their original characters for free. - An application may include characters already equal to their target characters, but all positions it covers still become used. ### What a Strong Answer Covers - Enforcing position reuse restrictions as well as pattern matching. - Accounting for every wildcard's fee and using replacements exactly as written. - Finding the minimum across different disjoint choices, including unchanged positions and impossible conversions.