1639. Number of Ways to Form a Target String Given a Dictionary - Detailed Explanation
Problem Statement
You are given a list of words, where each word has the same length m, and a string target. You need to determine how many ways you can form the target string by selecting one letter from each column of the words array. Each column in words represents a position from which you can pick a character (one from any word in that column). Return the number of ways modulo 10^9 + 7 (to handle large results).
Example 1:
Input:
words = ["acca", "bbbb", "caca"] target = "aba"
Output:
6
Explanation: There are 6 ways to form "aba" by picking letters from each column:
- 'a' from "acca", 'b' from "bbbb", 'a' from "acca"
- 'a' from "acca", 'b' from "bbbb", 'a' from "caca"
- 'a' from "acca", 'b' from "bbbb", 'a' from "caca"
- 'a' from "acca", 'b' from "bbbb", 'a' from "acca"
- 'a' from "caca", 'b' from "bbbb", 'a' from "acca"
- 'a' from "caca", 'b' from "bbbb", 'a' from "caca"
(Each bullet shows one possible selection of letters from the columns of the words list to form "aba".)
Constraints:
1 <= words.length <= 10001 <= words[i].length, target.length <= 100words[i]consists of lowercase English letters.targetconsists of lowercase English letters.
Hints to Solve the Problem
- Brute Force Approach: Consider generating all possible sequences of characters (by choosing one character from each column) and check which ones match the
target. This is a direct approach but becomes inefficient as the size of input grows. - Optimized Approach: Use dynamic programming (DP). Precompute the frequency of each character in each column of
words. Then, use DP to count ways to form the target by iterating through target characters and columns.
Approach 1: Brute Force (Exhaustive Search)
Explanation:
This approach tries all possible ways of picking characters from the columns and counts the ones that form the target. We can use recursion or DFS to explore every combination:
- Recursively go through each column index and try to match the current target character with letters from that column.
- If a word in the current column has the required character for the current position of
target, include that choice and move to the next character oftarget(and next column). - Also, consider the possibility of skipping the current column (not taking any character from this column for the target) and move to the next column.
- Count all the combinations that successfully build the entire target string.
This brute force approach is straightforward but inefficient for large inputs because it explores every combination of choices (exponential time).
Python Code (Brute Force)
Complexity Analysis (Brute Force)
- Time Complexity: Exponential, approximately O(2^m) in the worst case (where
mis the number of columns), because for each column, we decide to use it or skip it. - Space Complexity: O(m + n) due to the recursion stack.
Java Code (Brute Force):
Approach 2: Optimized Dynamic Programming (Frequency Count per Column)
Explanation:
To overcome the inefficiency of brute force, we use dynamic programming with precomputed character frequencies:
-
Precompute Frequencies: First, count how many of each letter appears in each column of
words. For example, in column 0 ofwords, count how many'a','b','c', etc. appear among all the words. Store these counts in a 2D arrayfreq[column_index][char]. -
DP State Definition: Use a DP table
dp[i][j]where:irepresents how many characters of the target have been formed so far (considering target prefix of lengthi).jrepresents how many columns ofwordshave been considered so far.dp[i][j]is the number of ways to form the firsticharacters of the target using the firstjcolumns ofwords.
-
DP Transitions:
-
If we do not use the j-th column, then
dp[i][j]can take all the ways fromdp[i][j-1](skip this column). -
If we use the j-th column to contribute to the i-th character of target, then we look at the previous state
dp[i-1][j-1](formed first i-1 target chars with j-1 columns) and multiply it by the number of ways we can get the i-th target character from column j. The number of ways to get a specific character from column j is given by our precomputedfreq. -
Therefore:
dp[i][j] = dp[i][j-1] + (dp[i-1][j-1] * freq[j-1][ target[i-1] ])
(Herefreq[j-1][ target[i-1] ]is the count of the charactertarget[i-1]in columnj-1ofwords. We usej-1andi-1as indices because our DP table indices are 1-based for lengths.)
-
-
Initialization:
dp[0][j] = 1for all j, because there is exactly 1 way to form an empty target (do nothing, regardless of how many columns are considered). -
We iterate through target length
nand columnsmto fill the DP table. The answer will bedp[n][m]— the number of ways to form allncharacters of target using allmcolumns. -
We apply modulo
10^9+7at each addition or multiplication step to keep numbers within bounds.
This DP approach efficiently counts combinations without brute-forcing all sequences.
Python Code (Optimized DP)
Complexity Analysis (Optimized DP)
- Time Complexity: O(n * m) for filling the DP table plus O(m * 26) for building the frequency table.
- Space Complexity: O(n * m) for the DP table and O(m * 26) for the frequency table.
Java Code (DP Solution):
Edge Cases
- Minimum Input:
- When
wordshas one word of length 1 andtargetis a single character. - Example:
words = ["a"],target = "a"→ Output:1.
- When
- No Possible Formation:
- If none of the columns contain the needed character at a particular target position, the output is
0.
- If none of the columns contain the needed character at a particular target position, the output is
- All Columns Identical:
- When every column is the same, the number of ways depends on the frequency of the required character in each column.
Common Mistakes
- Brute Force Pitfall:
Not pruning search branches early can lead to a timeout for larger inputs. - DP Indexing:
Off-by-one errors are common when translating between 0-indexed Python lists and conceptual 1-indexed DP tables. - Modulo Operations:
Failing to apply the modulo (10^9+7) at every addition or multiplication step, which can result in integer overflow.
Related Problems for Practice
- Word Break: Splitting a string into valid words using a dictionary.
- Count Ways to Decode: Counting ways to decode a numeric string to alphabets (DP-based counting).
- Subsequence Counting Problems: Such as counting distinct subsequences in a string.
GET YOUR FREE
Coding Questions Catalog
