Number of Ways to Form a Target String Given a Dictionary - Video Solutions

Problem Overview: You are given a list of equal-length words and a target string. Characters must be chosen column by column across the dictionary to build the target. Once you move past a column, you cannot reuse earlier columns. The task is to count how many distinct ways the target can be formed.

Approach 1: Memoization with Recursive Choices (Time: O(m * t + n * m), Space: O(m * t))

This approach models the problem as a recursive decision process. At each step you decide whether to use the current column to match the next target character or skip the column entirely. A memoization table caches states defined by (targetIndex, columnIndex) so repeated subproblems are avoided. To make matching efficient, you precompute how many times each character appears in every column of the dictionary. This converts each recursive step into a constant-time lookup rather than scanning all words.

The recurrence multiplies the number of ways a column can supply the required character with the number of ways to build the remaining suffix. Skipping the column moves to the next column without advancing the target index. This turns an exponential brute force search into a manageable dynamic programming problem.

Approach 2: Dynamic Programming with Character Frequency Table (Time: O(n * m + m * t), Space: O(t))

This is the optimized bottom-up solution. First compute a frequency table where freq[c][j] stores how many words contain character c at column j. Building this table costs O(n * m), where n is the number of words and m is the word length.

Then use dynamic programming where dp[i] represents the number of ways to build the first i characters of the target. Iterate through dictionary columns from left to right. For each column, update the DP array backwards so previously computed states are not overwritten. If the column contains the needed character, multiply the frequency by the number of ways to form the previous prefix. This effectively counts how many valid column selections produce each prefix of the target.

The backward update is the key insight: it preserves earlier DP states and ensures each column contributes only once per target position. The result is stored in dp[targetLength]. This solution is efficient because it compresses the 2D DP state into a single array while still respecting column order.

Recommended for interviews: The dynamic programming solution with a character frequency table is what most interviewers expect. It demonstrates strong understanding of dynamic programming, efficient preprocessing with arrays, and careful iteration over string positions. The memoization approach is useful to explain first because it shows the natural recurrence before optimizing to the iterative DP.