LeetCode in Kotlin

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

class Solution {
    fun minCost(source: String, target: String, rules: MutableList<MutableList<String>>, costs: IntArray): Int {
        val n = source.length
        if (n != target.length) {
            return -1
        }
        if (source == target) {
            return 0
        }
        val m = rules.size
        val len = IntArray(m)
        val pat = arrayOfNulls<String>(m)
        val rep = arrayOfNulls<String>(m)
        val rulesCost = IntArray(m)
        for (i in 0..<m) {
            val p = rules[i][0]
            val r: String = rules[i][1]
            pat[i] = p
            rep[i] = r
            len[i] = p.length
            var wild = 0
            for (c in p.toCharArray()) {
                if (c == '*') {
                    wild++
                }
            }
            rulesCost[i] = costs[i] + wild
        }
        val `in` = Int.MAX_VALUE / 2
        val dp = IntArray(n + 1)
        dp.fill(`in`)
        dp[0] = 0
        for (i in 0..<n) {
            if (dp[i] == `in`) {
                continue
            }
            if (source[i] == target[i] && dp[i] < dp[i + 1]) {
                dp[i + 1] = dp[i]
            }
            for (k in 0..<m) {
                val l = len[k]
                if (i + l > n) {
                    continue
                }
                var match = true
                for (j in 0..<l) {
                    val pc = pat[k]!![j]
                    val sc = source[i + j]
                    if (pc != '*' && pc != sc) {
                        match = false
                        break
                    }
                }
                if (!match) {
                    continue
                }
                if (target.substring(i, i + l) != rep[k]) {
                    continue
                }
                val nd = dp[i] + rulesCost[k]
                if (nd < dp[i + l]) {
                    dp[i + l] = nd
                }
            }
        }
        return if (dp[n] >= `in`) -1 else dp[n]
    }
}