3213. Construct String with Minimum Cost

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

C++JavaPython

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;
  }
};

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;
  }
}

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