Minimum number of valid strings to form target i

Array String Binary Search Dynamic Programming Trie Segment Tree Rolling Hash String Matching Hash Function

21.7% acceptance

Feb 25, 2026

176

You are given an array of strings words and a string target. A string x is called valid if x is a prefix of any string in words. Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
    let t = target.as_bytes();
    let n = t.len();
    // Trie to find max prefix length at each position in target
    // Use KMP-like: build a trie, then for each position find max extension
    // Or: for each position i in target, find max len extension using a trie traversal
    
    // Build trie
    // Node: children[26]
    struct Trie {
      children: Vec<[i32; 26]>,
    }
    impl Trie {
      fn new() -> Self { Trie { children: vec![[-1i32; 26]] } }
      fn insert(&mut self, s: &[u8]) {
        let mut node = 0usize;
        for &c in s {
          let idx = (c - b'a') as usize;
          if self.children[node][idx] == -1 {
            self.children[node][idx] = self.children.len() as i32;
            self.children.push([-1i32; 26]);
          }
          node = self.children[node][idx] as usize;
        }
      }
      fn max_prefix_from(&self, s: &[u8], start: usize) -> usize {
        let mut node = 0usize;
        let mut len = 0;
        for i in start..s.len() {
          let idx = (s[i] - b'a') as usize;
          if self.children[node][idx] == -1 { break; }
          node = self.children[node][idx] as usize;
          len += 1;
        }
        len
      }
    }
    
    let mut trie = Trie::new();
    for w in &words {
      trie.insert(w.as_bytes());
    }
    
    // dp[i] = min valid strings to cover target[0..i]
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 0..n {
      if dp[i] == i32::MAX { continue; }
      let max_len = trie.max_prefix_from(t, i);
      for l in 1..=max_len {
        if dp[i + l] > dp[i] + 1 {
          dp[i + l] = dp[i] + 1;
        }
      }
    }
    if dp[n] == i32::MAX { -1 } else { dp[n] }
  }
}