We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Convert String I

Difficulty: Medium

Problem Description

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i]. Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.

Key Insights

  • Each character in source can be changed to a corresponding character in target if there is a valid transformation defined by original, changed, and cost.
  • The problem can be viewed as a graph where each character is a node and an edge exists between two nodes if one can be transformed into the other at a specific cost.
  • Use a mapping to keep track of the minimum cost for each transformation.
  • If any character in target cannot be achieved from source, return -1.

Space and Time Complexity

Time Complexity: O(n + m^2), where n is the length of the source/target strings and m is the number of transformations defined in original/changed arrays.
Space Complexity: O(m + 26), where m is the number of transformations and 26 accounts for the lowercase English letters.

Solution

To solve the problem, we can use a graph representation where each character is a node. We will build an adjacency list that maps each character to its possible transformations along with the associated costs. We can then perform a shortest-path search (like Dijkstra's algorithm) to find the minimum cost for each character in source to transform into the corresponding character in target. If any character transformation is impossible, we return -1.

Code Solutions

from collections import defaultdict
import heapq

def minCost(source, target, original, changed, cost):
    if len(source) != len(target):
        return -1

    graph = defaultdict(list)
    for o, c, co in zip(original, changed, cost):
        graph[o].append((c, co))

    total_cost = 0
    for s, t in zip(source, target):
        if s == t:
            continue

        # Dijkstra's algorithm to find the minimum cost to change s to t
        min_cost = float('inf')
        pq = [(0, s)]  # (cost, character)
        visited = set()

        while pq:
            current_cost, char = heapq.heappop(pq)
            if char in visited:
                continue
            visited.add(char)

            if char == t:
                min_cost = current_cost
                break

            for neighbor, change_cost in graph[char]:
                if neighbor not in visited:
                    heapq.heappush(pq, (current_cost + change_cost, neighbor))

        if min_cost == float('inf'):
            return -1
        
        total_cost += min_cost

    return total_cost
← Back to All Questions