LeetCode Entry

1639. Number of Ways to Form a Target String Given a Dictionary

16.04.2023 hard 2023 kotlin

precompute the freq array - count of each character at each position

1639. Number of Ways to Form a Target String Given a Dictionary hard

fun numWays(words: Array<String>, target: String): Int {
    val freq = Array(words[0].length) { LongArray(26) }
    for (i in 0..words[0].lastIndex)
    words.forEach { freq[i][it[i].toInt() - 'a'.toInt()]++ }

    val cache = Array(words[0].length) { LongArray(target.length) { -1L } }
    val m = 1_000_000_007L

    fun dfs(wpos: Int, tpos: Int): Long {
        if (tpos == target.length) return 1L
        if (wpos == words[0].length) return 0L
        if (cache[wpos][tpos] != -1L) return cache[wpos][tpos]
        val curr = target[tpos].toInt() - 'a'.toInt()
        val currFreq = freq[wpos][curr]
        val take = if (currFreq == 0L) 0L else
        dfs(wpos + 1, tpos + 1)
        val notTake = dfs(wpos + 1, tpos)
        val mul = (currFreq * take) % m
        val res = (mul + notTake) % m
        cache[wpos][tpos] = res
        return res
    }
    return dfs(0, 0).toInt()
}

blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/182

Intuition

Consider an example: bbc aaa ccc, target = ac. We have 5 ways to form the ac:

// bbc aaa ccc   ac
//     a    c
//     a     c
//   c a
//      a    c
//   c  a

Looking at this, we deduce, that only count of every character at every position matter.

// 0 -> 1b 1a 1c
// 1 -> 1b 1a 1c
// 2 ->    1a 2c

To form ac we can start from position 0 or from 1. If we start at 0, we have one c at 1 plus two c at 2. And if we start at 1 we have two c at 3. \(DP_{i,j} = Freq * DP_{i + 1, j + 1} + DP_{i + 1, j}\)

Approach

• precompute the freq array - count of each character at each position
• use an Array for faster cache
• use long to avoid overflow

  Complexity

• Time complexity: \(O(n^2)\)
• Space complexity: \(O(n^2)\)