Problem Statement in English

You’re given two strings source and target of equal length consisting of lowercase English letters. You are also given three arrays original, changed, and cost, each of length m, where the i-th operation allows you to convert the character original[i] into the character changed[i] at a cost of cost[i].

Your task is to determine the minimum total cost required to convert the string source into the string target using the given operations. If it is impossible to convert source into target, return -1.

Approach

You could actually just use dijkstra’s algorithm for each character in source to find the minimum cost to convert it to the corresponding character in target.

However, since there are only 26 lowercase English letters, we can use the Floyd-Warshall algorithm to precompute the minimum cost to convert any character to any other character.

The main intuition behind Floyd-Warshall is that for each pair of nodes (i, j), we check if there exists an intermediate node k such that the path from i to k to j is cheaper than the direct path from i to j. If it is, we update the cost for the path from i to j.

Solution in Python


def minimumCost(source, target, original, changed, cost):
    INF = float('inf')
    
    # Step 1: distance matrix
    dist = [[INF] * 26 for _ in range(26)]
    
    for i in range(26):
        dist[i][i] = 0
    
    # Step 2: insert edges
    for o, c, w in zip(original, changed, cost):
        oi = ord(o) - ord('a')
        ci = ord(c) - ord('a')
        dist[oi][ci] = min(dist[oi][ci], w)
    
    # Step 3: Floyd-Warshall
    for k in range(26):
        for i in range(26):
            if dist[i][k] == INF:
                continue
            for j in range(26):
                if dist[k][j] == INF:
                    continue
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # Step 4: compute answer
    ans = 0
    for s, t in zip(source, target):
        si = ord(s) - ord('a')
        ti = ord(t) - ord('a')
        
        if dist[si][ti] == INF:
            return -1
        
        ans += dist[si][ti]
    
    return ans

Complexity

  • Time: $O(26^3 + n)$

  • Space: $O(26^2)$
    Since we store the distance matrix. This contains the distance from each character to every other character.

Mistakes I Made

I had to look up the Floyd-Warshall algorithm since I had forgotten how it works.

And we are done.