LeetCode-in-Java

3995. Minimum Cost to Convert String III

Hard

You are given two strings, source and target.

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

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

Since every patterni and replacementi 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.

Example 1:

Input: source = “hello”, target = “world”, rules = [[“he”,”wo”],[“llo”,”rld”]], costs = [3,4]

Output: 7

Explanation:

Example 2:

Input: source = “cat”, target = “dog”, rules = [[“c*t”,”dog”]], costs = [2]

Output: 3

Explanation:

Example 3:

Input: source = “test”, target = “next”, rules = [[”*e*t”,”next”]], costs = [4]

Output: 6

Explanation:

Example 4:

Input: source = “ab”, target = “bc”, rules = [[“a*”,”bd”]], costs = [9]

Output: -1

Explanation:

No sequence of rule applications can transform source into target, so the answer is -1.

Constraints:

Solution

import java.util.Arrays;
import java.util.List;

@SuppressWarnings("java:S135")
public class Solution {
    public int minCost(String source, String target, List<List<String>> rules, int[] costs) {
        int n = source.length();
        if (n != target.length()) {
            return -1;
        }
        if (source.equals(target)) {
            return 0;
        }
        int m = rules.size();
        int[] len = new int[m];
        String[] pat = new String[m];
        String[] rep = new String[m];
        int[] rulesCost = new int[m];
        for (int i = 0; i < m; i++) {
            String p = rules.get(i).get(0);
            String r = rules.get(i).get(1);
            pat[i] = p;
            rep[i] = r;
            len[i] = p.length();
            int wild = 0;
            for (char c : p.toCharArray()) {
                if (c == '*') {
                    wild++;
                }
            }
            rulesCost[i] = costs[i] + wild;
        }
        int in = Integer.MAX_VALUE / 2;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, in);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == in) {
                continue;
            }
            if (source.charAt(i) == target.charAt(i) && dp[i] < dp[i + 1]) {
                dp[i + 1] = dp[i];
            }
            for (int k = 0; k < m; k++) {
                int l = len[k];
                if (i + l > n) {
                    continue;
                }
                boolean match = true;
                for (int j = 0; j < l; j++) {
                    char pc = pat[k].charAt(j);
                    char sc = source.charAt(i + j);
                    if (pc != '*' && pc != sc) {
                        match = false;
                        break;
                    }
                }
                if (!match) {
                    continue;
                }
                if (!target.substring(i, i + l).equals(rep[k])) {
                    continue;
                }
                int nd = dp[i] + rulesCost[k];
                if (nd < dp[i + l]) {
                    dp[i + l] = nd;
                }
            }
        }
        return dp[n] >= in ? -1 : dp[n];
    }
}