LeetCode Problem 3213: Construct String with Minimum Cost You are given a string target,…
- User
LeetCode Problem 3213: Construct String with Minimum Cost
You are given a string
target, an array of stringswords, and an integer arraycosts, both arrays of the same length. Imagine an empty strings. You can perform the following operation any number of times (including zero):- Choose an index
iin the range[0, words.length - 1]. - Append
words[i]tos. - 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
sequal totarget. 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:7Example 2: Input:
target = "aaaa",words = ["z","zz","zzz"],costs = [1,10,100]Output:-1 - Choose an index
- 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
word2costto 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
word2costinto 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
dpof sizelen(target) + 1, wheredp[i]represents the minimum cost to construct the substringtarget[0:i]. - Base Case: Initialize
dp[0]to0since the cost to construct an empty string is zero.
4. DP State Transition:
- Iterate Over Target String: For each position
iintarget, 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 anddp[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-1in 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 - Dictionary Creation: Combine the words and costs into a dictionary