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

Construct String with Minimum Cost

Difficulty: Hard

Problem Description

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length. Imagine an empty string s. You can perform the following operation any number of times (including zero): choose an index i in the range [0, words.length - 1], append words[i] to s, and the cost of operation is costs[i]. Return the minimum cost to make s equal to target. If it's not possible, return -1.

Key Insights

  • The objective is to build the target string using the provided words at the minimum cost.
  • A dynamic programming approach can be used to keep track of the minimum cost to form each prefix of the target string.
  • For each character in the target, we can check all possible words that can contribute to forming that character and update the cost accordingly.
  • If a character in the target cannot be formed using any of the given words, we should return -1.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the target and m is the number of words.
Space Complexity: O(n), for storing the minimum costs for each prefix of the target.

Solution

To solve this problem, we use a dynamic programming approach. We maintain an array dp where dp[i] represents the minimum cost to form the prefix target[0...i-1]. We initialize dp[0] to 0 (cost to form an empty string is zero) and all other entries to infinity. For each character in the target, we consider all words to see if they can contribute to the current prefix. If they can, we update the cost in dp accordingly.

Code Solutions

def min_cost_to_construct_string(target, words, costs):
    n = len(target)
    m = len(words)
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # Cost to construct an empty string
    
    for i in range(1, n + 1):
        for j in range(m):
            word = words[j]
            cost = costs[j]
            word_length = len(word)
            if i >= word_length and target[i - word_length:i] == word:
                dp[i] = min(dp[i], dp[i - word_length] + cost)

    return dp[n] if dp[n] != float('inf') else -1
← Back to All Questions