i turns the substring rule_from[i] into rule_to[i] (of the same length) and costs rule_cost[i]. Any rule can be applied any number of times, and the same pair may appear with different prices.
You need to turn the string start into the string goal of the same length. Each rewrite applies to some segment of the current string. Any two segments you rewrite must either not overlap at all or be exactly the same: you may rewrite one segment several times in a row, but partially overlapping segments are forbidden.
Return the minimum total cost of the transformation, or -1 if it is impossible.start="cat", goal="cot", rule_from=["a", "e"], rule_to=["e", "o"], rule_cost=[2, 3] → 5
There is no direct rule a → o, but the same letter may be rewritten twice: a → e for 2, then e → o for 3. That is 5 in total.
start="abcd", goal="xycd", rule_from=["ab", "a", "b"], rule_to=["xy", "x", "y"], rule_cost=[5, 1, 1] → 2
Replacing the letters one by one, a → x and b → y, costs 1 + 1 = 2, which beats rewriting ab as a whole for 5.
start="aaa", goal="bbb", rule_from=["aa"], rule_to=["bb"], rule_cost=[1] → -1
The rule only changes a pair of letters. Covering three positions with pairs needs an overlap, and overlapping segments are not allowed, so the answer is -1.
start="cat", goal="cot", rule_from=["a", "e"], rule_to=["e", "o"], rule_cost=[2, 3]
5
Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.