Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

LeetCode Problem 3213: Construct String with Minimum Cost You are given a string target,…

  1. User

    LeetCode Problem 3213: Construct String with Minimum Cost

    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.
    • The cost of operation is costs[i].
    class Solution:
        def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
    

    Return the minimum cost to make s equal to target. If it's not possible, return -1.

    Example 1: Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5] Output: 7

    Example 2: Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100] Output: -1

  2. Assistant

    To solve this problem efficiently, we need to find the minimum cost to reconstruct the target string using given words and their associated costs. This problem can be reduced to a variant of the Word Break problem with the incorporation of costs.

    Here's a step-by-step plan for solving the problem:

    1. Preprocess the Words and Costs:

    • Dictionary Creation: Combine the words and costs into a dictionary word2cost to map each unique word to its minimum cost. If a word appears multiple times with different costs, we store the minimum cost among them.
    • Determine Maximum Word Length: Find the maximum length among all the words. This will help in limiting the search window when matching words against the target string.

    2. Build a Trie Data Structure:

    • Purpose of Trie: A trie (prefix tree) allows us to efficiently search for all words that can start at a particular position in the target string. This is crucial because we need to consider all possible substrings starting from each position in the target.
    • Trie Construction: Insert all words from word2cost into the trie. Each node will represent a character, and words ending at a node are marked accordingly.

    3. Dynamic Programming (DP) Initialization:

    • DP Array: Create a DP array dp of size len(target) + 1, where dp[i] represents the minimum cost to construct the substring target[0:i].
    • Base Case: Initialize dp[0] to 0 since the cost to construct an empty string is zero.

    4. DP State Transition:

    • Iterate Over Target String: For each position i in target, we attempt to match as many words as possible starting from that position using the trie.
    • Trie Traversal: We traverse the trie starting from the root node, moving to child nodes matching the current character in the target string.
    • Update DP Array: Whenever we find a word that ends at a certain position, we update dp[end_index] to the minimum of its current value and dp[start_index] + cost_of_word.

    5. Result Determination:

    • Check Final DP Value: If dp[len(target)] is still infinity (or a large number representing it), it means it's impossible to construct the target string with the given words. Return -1 in this case.
    • Return Minimum Cost: Otherwise, return dp[len(target)] as it holds the minimum cost to construct the entire target string.

    Below is the implementation of the above plan:

    from typing import List
    import sys
    sys.setrecursionlimit(1 << 25)
    
    class TrieNode:
        def __init__(self):
            self.children = dict()
            self.word_end = False
            self.word = ''
            self.cost = 0
    
    class Solution:
        def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
            # Preprocess words and costs
            word2cost = dict()
            for word, cost in zip(words, costs):
                if word not in word2cost or cost < word2cost[word]:
                    word2cost[word] = cost
    
            # Build trie
            root = TrieNode()
            for word, cost in word2cost.items():
                node = root
                for c in word:
                    if c not in node.children:
                        node.children[c] = TrieNode()
                    node = node.children[c]
                node.word_end = True
                node.word = word
                node.cost = cost
    
            n = len(target)
            dp = [float('inf')] * (n +1)
            dp[0] = 0
    
            for i in range(n):
                if dp[i] == float('inf'):
                    continue
                node = root
                j = i
                while j < n and target[j] in node.children:
                    node = node.children[target[j]]
                    j +=1
                    if node.word_end:
                        dp[j] = min(dp[j], dp[i] + node.cost)
            return dp[n] if dp[n] != float('inf') else -1