# 29.12.2024 [1639. Number of Ways to Form a Target String Given a Dictionary]

Ways to make target with increasing positions in words #hard #dynamic_programming

29.12.2024

1639. Number of Ways to Form a Target String Given a Dictionary hard blog post youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/847

Problem TLDR

Ways to make target with increasing positions in words #hard #dynamic_programming

Intuition

Let's observe an example at different angles:

    // acca bbbb caca     aba
    // a    .b   ...a
    // a    ..b  ...a
    // a..a .b   ....
    // a..a ..b. ....
    // ...a ..b. .a
    //      ..b  .a.a

    // 0123
    //    a
    // aa a
    // bbbb
    // ccc
    //   c

    //  0 1 2    2 1 0    1 2 0    0 2 1
    // [a,b,c]->[a,b,c]->[b,c,c]->[a,a,b]
    // aba
    //  *          *               *
    //  *          *                 *
    //  *                 *        *
    //  *                 *          *
    //           *        *        *
    //           *        *          *

Each position i in words[..] have a set of chars words[..][i]. We can use a full Depth-First Search and take or drop the current position. To count total ways, we should multiply by count of the taken chars at position. Result can be safely cached by (i, target_pos) key.

Approach

• we can rewrite top-down DFS + memo into iterative bottom-up DP

• as we only depend on the next (or previous) positions, we can collapse 2D dp into 1D

• some other small optimizations possible, iterate forward for cache-friendliness

Complexity

• Time complexity: $$O(wt)$$

• Space complexity: $$O(t)$$

Code

    fun numWays(words: Array<String>, target: String): Int {
        val fr = Array(words[0].length) { IntArray(26) }
        for (w in words) for (i in w.indices) fr[i][w[i] - 'a']++
        val dp = Array(fr.size + 1) { LongArray(target.length + 1) { -1L }}
        fun dfs(posF: Int, posT: Int): Long = dp[posF][posT].takeIf { it >= 0 } ?: {
            if (posT == target.length) 1L else if (posF == fr.size) 0L else {
                val notTake = dfs(posF + 1, posT)
                val curr = fr[posF][target[posT] - 'a'].toLong()
                val take = if (curr > 0) curr * dfs(posF + 1, posT + 1) else 0
                (take + notTake) % 1_000_000_007L
            }}().also { dp[posF][posT] = it }
        return dfs(0, 0).toInt()
    }

    pub fn num_ways(words: Vec<String>, target: String) -> i32 {
        let mut dp = vec![0; target.len() + 1]; dp[target.len()] = 1;
        let M = 1_000_000_007i64; let target: Vec<_> = target.bytes().rev().collect();
        for posF in 0..words[0].len() {
            let mut fr = vec![0; 26]; 
            for w in &words { fr[(w.as_bytes()[posF] - b'a') as usize] += 1 }
            for (posT, t) in target.iter().enumerate() {
                dp[posT] += fr[(t - b'a') as usize] * dp[posT + 1] % M
            }
        }; (dp[0] % M) as i32
    }

    int numWays(vector<string>& words, string target) {
        long d[10001] = { 1 }, M = 1e9 + 7;
        for (int i = 0; i < words[0].size(); ++i) {
            int f[26] = {}; for (auto &w: words) ++f[w[i] - 97];
            for (int j = min(i + 1, (int) target.size()); j; --j) 
                d[j] += f[target[j - 1] - 97] * d[j - 1] % M;
        } return d[target. Size()] % M;
    }