3213. Construct String with Minimum Cost LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3213. Construct String with Minimum Cost LeetCode Solution with the best time and space complexity. The solution to Construct String with Minimum Cost problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct String with Minimum Cost solution in C++
Construct String with Minimum Cost solution in Java
Construct String with Minimum Cost solution in Python
Additional Resources

3213. Construct String with Minimum Cost LeetCode Solution image

Problem Statement of 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].

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
Explanation:
The minimum cost can be achieved by performing the following operations:

Select index 1 and append “abc” to s at a cost of 1, resulting in s = “abc”.
Select index 2 and append “d” to s at a cost of 1, resulting in s = “abcd”.
Select index 4 and append “ef” to s at a cost of 5, resulting in s = “abcdef”.

Example 2:

Input: target = “aaaa”, words = [“z”,”zz”,”zzz”], costs = [1,10,100]
Output: -1
Explanation:
It is impossible to make s equal to target, so we return -1.

Constraints:

1 <= target.length <= 5 * 104
1 <= words.length == costs.length <= 5 * 104
1 <= words[i].length <= target.length
The total sum of words[i].length is less than or equal to 5 * 104.
target and words[i] consist only of lowercase English letters.
1 <= costs[i] <= 104

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(\Sigma |\texttt{words[i]}|)

3213. Construct String with Minimum Cost LeetCode Solution in C++

class TrieNode {
 public:
  vector<shared_ptr<TrieNode>> children;
  int cost = INT_MAX;
  TrieNode() : children(26) {}
};

class Trie {
 public:
  // Inserts a word with a cost.
  void insert(const string& word, int cost) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
    }
    node->cost = min(node->cost, cost);
  }

  // Returns the minimum cost to construct s[i:].
  int search(const string& word, int i, vector<int>& mem) {
    if (i == word.size())
      return 0;
    if (mem[i] != INT_MAX)
      return mem[i];
    int cost = INT_MAX;
    shared_ptr<TrieNode> node = root;
    for (int j = i; j < word.length(); ++j) {
      const int index = word[j] - 'a';
      if (node->children[index] == nullptr)
        break;
      node = node->children[index];
      if (node->cost != INT_MAX) {
        const int childCost = search(word, j + 1, mem);
        if (childCost != INT_MAX)
          cost = min(cost, node->cost + childCost);
      }
    }
    return mem[i] = cost;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
};

class Solution {
 public:
  int minimumCost(string target, vector<string>& words, vector<int>& costs) {
    Trie trie;

    for (int i = 0; i < words.size(); ++i)
      trie.insert(words[i], costs[i]);

    vector<int> mem(target.size(), INT_MAX);
    const int ans = trie.search(target, 0, mem);
    return ans == INT_MAX ? -1 : ans;
  }
};
/* code provided by PROGIEZ */

3213. Construct String with Minimum Cost LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public int cost = Integer.MAX_VALUE;
}

class Trie {
  // Inserts a word with a cost.
  public void insert(String word, int cost) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.cost = Math.min(node.cost, cost);
  }

  // Returns the minimum cost to construct s[i:].
  public int search(final String word, int i, Integer[] mem) {
    if (i == word.length())
      return 0;
    if (mem[i] != null)
      return mem[i];
    int cost = Integer.MAX_VALUE;
    TrieNode node = root;
    for (int j = i; j < word.length(); ++j) {
      final int index = word.charAt(j) - 'a';
      if (node.children[index] == null)
        break;
      node = node.children[index];
      if (node.cost != Integer.MAX_VALUE) {
        final int childCost = search(word, j + 1, mem);
        if (childCost != Integer.MAX_VALUE)
          cost = Math.min(cost, node.cost + childCost);
      }
    }
    return mem[i] = cost;
  }

  private TrieNode root = new TrieNode();
}

class Solution {
  public int minimumCost(String target, String[] words, int[] costs) {
    Trie trie = new Trie();

    for (int i = 0; i < words.length; ++i)
      trie.insert(words[i], costs[i]);

    final int ans = trie.search(target, 0, new Integer[target.length()]);
    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}
// code provided by PROGIEZ

3213. Construct String with Minimum Cost LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}
    self.cost = math.inf


class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word: str, cost: int) -> None:
    """Inserts a word with a cost."""
    node: TrieNode = self.root
    for c in word:
      node = node.children.setdefault(c, TrieNode())
    node.cost = min(node.cost, cost)

  @functools.lru_cache(None)
  def search(self, word: str, i: int) -> int:
    """Returns the minimum cost to construct s[i:]."""
    if i == len(word):
      return 0
    cost = math.inf
    node = self.root
    for i in range(i, len(word)):
      if word[i] not in node.children:
        break
      node = node.children[word[i]]
      if node.cost != math.inf:
        childCost = self.search(word, i + 1)
        if childCost != math.inf:
          cost = min(cost, node.cost + childCost)
    return cost


class Solution:
  def minimumCost(self, target: str, words: list[str], costs: list[int]) -> int:
    trie = Trie()

    for word, cost in zip(words, costs):
      trie.insert(word, cost)

    ans = trie.search(target, 0)
    return -1 if ans == math.inf else ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents