3995. Minimum Cost to Convert String III

You are given two strings, source and target.

You are also given a 2D string array rules, where rules[i] = [pattern_i, replacement_i], and an integer array costs, where costs[i] is the base cost of applying rules[i]. Both arrays have the same length. Additionally, pattern_i and replacement_i have the same length.

You may apply any rule any number of times. Each rule application works as follows:

• Choose an index l such that the range of positions from l to l + pattern_i.length - 1 exists in the current string and none of these positions has been used in a previous rule application.
• For each index j, the character pattern_i[j] must either be equal to the current character at position l + j, or be '*'.
• Replace the characters in this range with replacement_i. The replacement is used exactly as given and does not contain wildcards.
• The cost of this rule application is costs[i] plus the number of '*' characters in pattern_i.
• Once a character position has been used in a rule application, it cannot be used in any later rule application.

Since every pattern_i and replacement_i have the same length, character positions are preserved after every rule application.

Return the minimum total cost required to transform source into target. If it is impossible, return -1.

class Solution {
public:
    int minCost(string source, string target, vector<vector<string>>& rules, vector<int>& costs) {
        int n = source.size();
        long long INF = 1e18;
        vector<long long> dp(n + 1, INF);
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            if(dp[i] == INF) continue;
            if(source[i] == target[i]) dp[i+1] = min(dp[i+1], dp[i]);
            for(int j = 0; j < rules.size(); j++) {
                auto &rule = rules[j];
                string &p = rule[0], &r = rule[1];
                int len = p.length(), cost = costs[j];
                if (i + len > n) continue;
                bool ok = true;
                for (int k = 0; k < len and ok; k++) {
                    if (r[k] != target[i + k]) ok = false;
                    if (p[k] == '*') cost++;
                    else if (p[k] != source[i + k]) ok = false;
                }
                if (ok) dp[i + len] = min(dp[i + len], dp[i] + cost);
            }
        }
        return dp[n] == INF ? -1 : dp[n];
    }
};