Number of Ways to Form a Target String Given a Dictionary

LeetCode Number of Ways to Form a Target String Given a Dictionary (problem 1639) asks you to count how many distinct ways you can build a target string by picking characters from columns of a dictionary. It sounds simple at first, but the constraint on column ordering and the need for modular arithmetic make this a classic hard DP problem.

The problem

You are given a list of words, all the same length, and a target string. You want to form the target by picking one character at a time from the dictionary. The rule is: to pick the k-th character of the target, you choose any one of the words and take a character at some column index j. Every subsequent pick must come from a strictly higher column index. You cannot reuse the same column for two different target characters, and you must move left to right through the columns.

Return the number of ways to form the target, modulo 10^9 + 7.

The brute force approach

The first idea that comes to mind is to try every possible assignment of target characters to columns. For each character in the target, you scan through available columns (those after the previously used column) and check whether any word has a matching character at that position. You recurse on the remaining target characters.

This works for tiny inputs, but the number of recursive paths grows explosively. If the target has length m and the words have length n, you are essentially choosing m columns out of n in order. The number of such combinations is C(n, m), and for each you multiply by the character matches. Without memoization, the time complexity is exponential.

The key insight

You do not need to track which specific word you pick from. All that matters is how many words have the right character at a given column. If three words have the letter 'a' at column 2, then there are three ways to pick 'a' from column 2. The identity of the word is irrelevant.

This means you can precompute a frequency table: for each column index j and each character c, store the count of words that have c at position j. Once you have that table, the problem reduces to a pure DP over the target string and column positions.

Step-by-step walkthrough

The code

def num_ways(words, target):
    MOD = 10**9 + 7
    m = len(target)
    n = len(words[0])

    freq = [[0] * 26 for _ in range(n)]
    for word in words:
        for j, ch in enumerate(word):
            freq[j][ord(ch) - ord('a')] += 1

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

    for j in range(n):
        for i in range(min(m, j + 1), 0, -1):
            dp[i] = (dp[i] + dp[i - 1] * freq[j][ord(target[i - 1]) - ord('a')]) % MOD

    return dp[m]

The function starts by building the freq table. For each column j in the words, it counts how many words have each letter at that position. This takes O(n * number_of_words) time and gives you O(1) lookup for any (column, character) pair.

The DP uses a 1D array where dp[i] represents the number of ways to form the first i characters of the target using columns seen so far. It initializes dp[0] = 1 because there is exactly one way to form an empty target: pick nothing. Then for each column j, it iterates backward through the target indices and updates dp[i] by adding dp[i-1] * freq[j][target[i-1]]. Iterating backward ensures each column is used at most once per target character.

Complexity analysis

Here n is the length of each word, m is the length of the target, and k is the number of words. Building the frequency table takes O(n * k). The DP fills an array of size m + 1 for each of the n columns, giving O(n * m). The total time is O(n * k + n * m), and the space is O(26 * n) for the frequency table plus O(m) for the DP array.

The building blocks

Column frequency precomputation

The idea of collapsing individual elements into aggregate counts before running DP appears in many problems. Instead of reasoning about which specific word contributes a character, you count how many words contribute that character at each position. This is the same principle behind problems like Distinct Subsequences, where you count how many times a character appears rather than tracking exact positions.

1D DP with backward iteration

The trick of using a 1D array and iterating backward to avoid overwriting values you still need is a staple of knapsack-style DP. Each column acts like an "item" and each target character acts like a "capacity slot." By going from right to left in the inner loop, you guarantee that the value at dp[i-1] still reflects the state before the current column was considered. This is the same technique used in Edit Distance when optimizing from a 2D table to a 1D rolling array.

Edge cases

• Target longer than the word length. If len(target) > len(words[0]), there are not enough columns to assign one per target character. The answer is 0, and the DP handles this naturally because the inner loop never runs when j + 1 is smaller than i.
• No word has a needed character at any valid column. If some character in the target does not appear at any column index that could be assigned to it (given the ordering constraint), the DP stays at 0 for that suffix. This is handled by freq[j][c] being 0.
• All words are identical. The frequency at each column is either k (number of words) or 0. The DP still works, and the answer may be very large due to the k multiplier at every matching column.

From understanding to recall

The two pieces to internalize here are the frequency precomputation and the 1D backward DP. When you see a problem that says "pick from columns in order," your first instinct should be to ask: does the identity of the source matter, or just the count? If it is just the count, collapse it into a frequency table. Then the DP falls into a familiar knapsack shape.

Practice writing the solution from memory. Focus on the order of the loops (columns in the outer loop, target indices backward in the inner loop) and the update rule (dp[i] += dp[i-1] * freq[j][char]). Once those two details feel automatic, you can reconstruct the full solution in an interview without hesitation.

Related posts

• Distinct Subsequences - Another counting DP where you track how many ways to form a subsequence from a source string
• Edit Distance - Classic 2D DP on two strings with the same backward-iteration optimization trick
• Word Break - DP over a target string using a dictionary, a related structural pattern