Number of Ways to Form a Target String Given a Dictionary

How it works

Since we only need the previous row of the DP table to compute the current row, we can reduce space by using a single 1D array.

Steps

1. Precompute the character frequency table.
2. Use a 1D DP array of size m + 1.
3. Iterate from i = n down to 0, and for each row, iterate through columns in reverse.
4. Maintain the value from the next row using a temporary variable.
5. Return dp[0] modulo 10^9 + 7.

Complexity

• Time complexity: O(m * (n + N))
• Space complexity: O(m)

Where N is the number of words, m is the length of each word, and n is the length of the target string.

Things to watch for

Forgetting to Precompute Character Frequencies

A common mistake is iterating through all words at each step to count matching characters. This leads to TLE because the time complexity becomes O(N) per state transition. Instead, precompute a frequency table cnt[k][c] storing how many words have character c at column k before starting the DP.

Integer Overflow When Multiplying Count by DP Value

When computing cnt[k][c] * dp[i+1][k+1], both values can be large. In languages like Java and C++, multiplying two int values can overflow before the modulo operation is applied. Always cast to long or long long before multiplication: (long) cnt[k][c] * dp[i+1][k+1] % MOD.

Using Wrong Base Case for Bottom-Up DP

In bottom-up DP, the base case placement matters. Setting dp[n][k] = 1 for all k is incorrect because only dp[n][m] = 1 represents a valid completion (target fully matched at the end). The recurrence dp[i][k] = dp[i][k+1] propagates this value correctly, but initializing all dp[n][k] = 1 would overcount.

Confusing Column Index with Target Index

The DP state involves two indices: i for the target position and k for the column in words. A common error is swapping their roles or forgetting that k can skip ahead (we can skip columns) while i must advance exactly by 1 each time we pick a character. The column index k must always be at least as large as the target index i.

Not Handling Target Longer Than Word Length

If the target string is longer than the word length (n > m), it is impossible to form the target since we need at least n columns. The algorithm should return 0 in this case. While the recursion handles this naturally (running out of columns before finishing target), explicitly checking can prevent unnecessary computation.

from typing import List

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 10**9 + 7
        n, m = len(target), len(words[0])

        cnt = [[0] * 26 for _ in range(m)]
        for word in words:
            for i, c in enumerate(word):
                cnt[i][ord(c) - ord('a')] += 1

        dp = [0] * (m + 1)
        dp[m] = 1

        for i in range(n, -1, -1):
            nxt = 1 if i == n - 1 else 0
            for k in range(m - 1, -1, -1):
                cur = dp[k]
                dp[k] = dp[k + 1]
                if i < n:
                    c = ord(target[i]) - ord('a')
                    dp[k] = (dp[k] + cnt[k][c] * nxt) % MOD
                nxt = cur
            dp[m] = 0

        return dp[0]

class Solution {
private:
    static const int MOD = 1e9 + 7;

public:
    int numWays(vector<string>& words, string target) {
        int n = target.size(), m = words[0].size();

        vector<vector<int>> cnt(m, vector<int>(26, 0));
        for (const string& word : words) {
            for (int i = 0; i < word.size(); i++) {
                cnt[i][word[i] - 'a']++;
            }
        }

        vector<int> dp(m + 1);
        dp[m] = 1;

        for (int i = n; i >= 0; i--) {
            int nxt = i == n - 1 ? 1 : 0;
            for (int k = m - 1; k >= 0; k--) {
                int cur = dp[k];
                dp[k] = dp[k + 1];
                if (i < n) {
                    int c = target[i] - 'a';
                    dp[k] = (dp[k] + (long long) cnt[k][c] * nxt) % MOD;
                }
                nxt = cur;
            }
            dp[m] = 0;
        }

        return dp[0];
    }
};