Construct string with minimum cost

Array String Dynamic Programming Suffix Array

19.0% acceptance

Feb 25, 2026

172

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 {
    const INF: i32 = i32::MAX / 2;
    let n = target.len();
    let tb = target.as_bytes();

    // Build Aho-Corasick automaton
    // ch[node][c] = next state on character c
    // word_cost[node] = min cost of word ending here (0 = no word, costs >= 1)
    // word_len[node]  = length of the word ending here
    let mut ch: Vec<[usize; 26]> = vec![[usize::MAX; 26]; 1];
    let mut word_cost: Vec<i32> = vec![0];
    let mut word_len:  Vec<usize> = vec![0];

    for (word, &cost) in words.iter().zip(costs.iter()) {
      let mut cur = 0;
      for &b in word.as_bytes() {
        let c = (b - b'a') as usize;
        if ch[cur][c] == usize::MAX {
          ch[cur][c] = ch.len();
          ch.push([usize::MAX; 26]);
          word_cost.push(0);
          word_len.push(0);
        }
        cur = ch[cur][c];
      }
      let wl = word.len();
      if word_cost[cur] == 0 || cost < word_cost[cur] {
        word_cost[cur] = cost;
        word_len[cur] = wl;
      }
    }

    let sz = ch.len();
    let mut fail = vec![0usize; sz];
    let mut dict_suf = vec![0usize; sz]; // closest ancestor suffix that is a word

    // BFS to build fail links and complete automaton
    let mut queue = std::collections::VecDeque::new();
    for c in 0..26 {
      if ch[0][c] == usize::MAX {
        ch[0][c] = 0;
      } else {
        let v = ch[0][c];
        fail[v] = 0;
        dict_suf[v] = 0;
        queue.push_back(v);
      }
    }
    while let Some(u) = queue.pop_front() {
      for c in 0..26 {
        if ch[u][c] == usize::MAX {
          ch[u][c] = ch[fail[u]][c];
        } else {
          let v = ch[u][c];
          fail[v] = ch[fail[u]][c];
          dict_suf[v] = if word_cost[fail[v]] > 0 {
            fail[v]
          } else {
            dict_suf[fail[v]]
          };
          queue.push_back(v);
        }
      }
    }

    // DP over the target string
    let mut dp = vec![INF; n + 1];
    dp[0] = 0;
    let mut state = 0usize;

    for i in 1..=n {
      state = ch[state][(tb[i - 1] - b'a') as usize];
      // Collect all word matches ending at i via state and dict_suf chain
      let mut v = state;
      loop {
        if word_cost[v] > 0 {
          let l = word_len[v];
          if i >= l && dp[i - l] < INF {
            let cand = dp[i - l] + word_cost[v];
            if cand < dp[i] { dp[i] = cand; }
          }
        }
        if dict_suf[v] == 0 { break; }
        v = dict_suf[v];
      }
    }

    if dp[n] == INF { -1 } else { dp[n] }
  }
}