Construct string with minimum cost easy

58.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(target: String, words: Vec<String>, costs: Vec<i32>) -> i32 {
    let target = target.as_bytes();
    let n = target.len();

    let mut trie: Vec<[i32; 26]> = vec![[-1; 26]; 1];
    let mut trie_cost: Vec<i32> = vec![i32::MAX];

    for (idx, word) in words.iter().enumerate() {
      let mut node = 0;
      for &b in word.as_bytes() {
        let c = (b - b'a') as usize;
        if trie[node][c] == -1 {
          trie[node][c] = trie.len() as i32;
          trie.push([-1; 26]);
          trie_cost.push(i32::MAX);
        }
        node = trie[node][c] as usize;
      }
      trie_cost[node] = trie_cost[node].min(costs[idx]);
    }

    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;

    for i in 0..n {
      if dp[i] == i32::MAX {
        continue;
      }
      let mut node = 0;
      for j in i..n {
        let c = (target[j] - b'a') as usize;
        if trie[node][c] == -1 {
          break;
        }
        node = trie[node][c] as usize;
        if trie_cost[node] != i32::MAX {
          dp[j + 1] = dp[j + 1].min(dp[i].saturating_add(trie_cost[node]));
        }
      }
    }

    if dp[n] == i32::MAX { -1 } else { dp[n] }
  }
}