How hard is LeetCode 2977. Minimum Cost to Convert String II?

LeetCode 2977. Minimum Cost to Convert String II is rated Hard on LeetCode.

What is the time complexity of LeetCode 2977. Minimum Cost to Convert String II?

The Python solution on this page runs in O(m^3 + n^2 + m \times n).

What is the space complexity of LeetCode 2977. Minimum Cost to Convert String II?

The Python solution on this page uses O(m^2 + m \times n + n) auxiliary space.

What topics does LeetCode 2977. Minimum Cost to Convert String II cover?

LeetCode 2977. Minimum Cost to Convert String II is tagged Graph, Trie, Array, String, Dynamic Programming and Shortest Path on LeetCode.

Minimum Cost to Convert String II — LeetCode 2977 Python Solution

HardGraphTrieArrayStringDynamic ProgrammingShortest Path

Problem: #2977
Pattern: Trie
Reading time: 12 min
Source: leetcode.com

The problem

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].

Example

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert "abcd" to "acbe", do the following operations:

Python solution

Python

class Node:
    __slots__ = ["children", "v"]

    def __init__(self):
        self.children: List[Node | None] = [None] * 26
        self.v = -1


class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int],
    ) -> int:
        m = len(cost)
        g = [[inf] * (m << 1) for _ in range(m << 1)]
        for i in range(m << 1):
            g[i][i] = 0
        root = Node()
        idx = 0

        def insert(w: str) -> int:
            node = root
            for c in w:
                i = ord(c) - ord("a")
                if node.children[i] is None:
                    node.children[i] = Node()
                node = node.children[i]
            if node.v < 0:
                nonlocal idx
                node.v = idx
                idx += 1
            return node.v

        @cache
        def dfs(i: int) -> int:
            if i >= len(source):
                return 0
            res = dfs(i + 1) if source[i] == target[i] else inf
            p = q = root
            for j in range(i, len(source)):
                p = p.children[ord(source[j]) - ord("a")]
                q = q.children[ord(target[j]) - ord("a")]
                if p is None or q is None:
                    break
                if p.v < 0 or q.v < 0:
                    continue
                res = min(res, dfs(j + 1) + g[p.v][q.v])
            return res

        for x, y, z in zip(original, changed, cost):
            x = insert(x)
            y = insert(y)
            g[x][y] = min(g[x][y], z)
        for k in range(idx):
            for i in range(idx):
                if g[i][k] >= inf:
                    continue
                for j in range(idx):
                    # g[i][j] = min(g[i][j], g[i][k] + g[k][j])
                    if g[i][k] + g[k][j] < g[i][j]:
                        g[i][j] = g[i][k] + g[k][j]

        ans = dfs(0)
        return -1 if ans >= inf else ans

Complexity

Measure	Complexity
Time	O(m^3 + n^2 + m \times n)
Space	O(m^2 + m \times n + n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 2977. Minimum Cost to Convert String II is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2977. Minimum Cost to Convert String II?: LeetCode 2977. Minimum Cost to Convert String II is rated Hard on LeetCode.
What is the time complexity of LeetCode 2977. Minimum Cost to Convert String II?: The Python solution on this page runs in O(m^3 + n^2 + m \times n).
What is the space complexity of LeetCode 2977. Minimum Cost to Convert String II?: The Python solution on this page uses O(m^2 + m \times n + n) auxiliary space.
What topics does LeetCode 2977. Minimum Cost to Convert String II cover?: LeetCode 2977. Minimum Cost to Convert String II is tagged Graph, Trie, Array, String, Dynamic Programming and Shortest Path on LeetCode.