Number of ways to form a target string given a dictionary

Array String Dynamic Programming

56.6% acceptance

Feb 25, 2026

2058

120

You are given a list of strings of the same length words and a string target. Your task is to form target using the given words under the following rules: target should be formed from left to right. To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k]. Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. Return the number of ways to form target from words. Since the answer may be too large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

const MOD: i64 = 1_000_000_007;

impl Solution {
  pub fn num_ways(words: Vec<String>, target: String) -> i32 {
    let w_len = words[0].len();
    let t_len = target.len();
    let target: Vec<usize> = target.bytes().map(|b| (b - b'a') as usize).collect();

    // cnt[j][c] = count of words with char c at position j
    let mut cnt = vec![[0i64; 26]; w_len];
    for word in &words {
      for (j, b) in word.bytes().enumerate() {
        cnt[j][(b - b'a') as usize] += 1;
      }
    }

    // dp[i] = ways to form first i chars of target using cols 0..j
    let mut dp = vec![0i64; t_len + 1];
    dp[0] = 1;
    for j in 0..w_len {
      // iterate backwards to avoid using same column twice
      for i in (1..=t_len.min(j + 1)).rev() {
        dp[i] = (dp[i] + dp[i-1] * cnt[j][target[i-1]]) % MOD;
      }
    }
    dp[t_len] as i32
  }
}