You are given a list of strings of the same length words and a string target.
Your task is to form target using the given words under the following rules:
target should be formed from left to right.ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.target.Notice that you can use multiple characters from the same string in words provided the conditions above are met.
Return the number of ways to form target from words. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")
Example 2:
Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 1000words have the same length.1 <= target.length <= 1000words[i] and target contain only lowercase English letters.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.
This approach utilizes dynamic programming along with a frequency table to keep track of the count of each character at each column index across the given words. We calculate ways to form the target string by building up solutions to subproblems of forming prefixes of the target string using the letter frequency information efficiently.
This solution constructs a DP table where `dp[i][j]` represents the number of ways to form the first `i` characters of the target using the first `j` characters (positions) of the words. The `count` table stores how many times each character appears at each position in `words`. We update the DP table row by row for each position in the target by combining counts from the `count` table and previous DP states.
Time Complexity: O(n*m + m*t), where n is the number of words, m is the length of each word, and t is the length of the target string.
Space Complexity: O(m*t).
This approach uses memoization to optimize the recursion while forming the target. We compute ways from each index of target and position of words and save computed results to avoid redundant calculations. This approach is effective in reducing the exponential time complexity without deep overlapping subproblems.
This solution employs a recursive depth-first search (`dfs`) with memoization. The function `dfs(i, j)` returns the number of ways to form the target string starting from index `i` of the target and index `j` of a word in `words`. The memoized `dp` array stores results of overlapping subproblems to avoid recalculations.
Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).
We noticed that the length of each string in the string array words is the same, so let's remember n, then we can preprocess a two-dimensional array cnt, where cnt[j][c] represents the string array words The number of characters c in the j-th position of.
Next, we design a function dfs(i, j), which represents the number of schemes that construct target[i,..] and the currently selected character position from words is j. Then the answer is dfs(0, 0).
The calculation logic of function dfs(i, j) is as follows:
i geq m, it means that all characters in target have been selected, then the number of schemes is 1.j geq n, it means that all characters in words have been selected, then the number of schemes is 0.j-th position of words, then the number of schemes is dfs(i, j + 1); or we choose the character in the j-th position of words, then the number of schemes is dfs(i + 1, j + 1) times cnt[j][target[i] - 'a'].Finally, we return dfs(0, 0). Note that the answer is taken in modulo operation.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m is the length of the string target, and n is the length of each string in the string array words.
Python
Java
C++
Go
TypeScript
Similar to Solution 1, we can first preprocess a two-dimensional array cnt, where cnt[j][c] represents the number of characters c in the j-th position of the string array words.
Next, we define f[i][j] which represents the number of ways to construct the first i characters of target, and currently select characters from the first j characters of each word in words. Then the answer is f[m][n]. Initially f[0][j] = 1, where 0 leq j leq n.
Consider f[i][j], where i \gt 0, j \gt 0. We can choose not to select the character in the j-th position of words, in which case the number of ways is f[i][j - 1]; or we choose the character in the j-th position of words, in which case the number of ways is f[i - 1][j - 1] times cnt[j - 1][target[i - 1] - 'a']. Finally, we add the number of ways in these two cases, which is the value of f[i][j].
Finally, we return f[m][n]. Note the mod operation of the answer.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m is the length of the string target, and n is the length of each string in the string array words.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Character Frequency Table | Time Complexity: O(n*m + m*t), where n is the number of words, m is the length of each word, and t is the length of the target string. |
| Memoization Approach | Time Complexity: O(n*m + m*t), optimized with memoization. |
| Preprocessing + Memory Search | — |
| Preprocessing + Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Memoization with Recursive Choices | O(n*m + m*t) | O(m*t) | When deriving the recurrence or explaining the DP state during interviews |
| Dynamic Programming with Character Frequency Table | O(n*m + m*t) | O(t) | Optimal solution for large inputs and production-quality implementations |
Number of Ways to Form a Target String Given a Dictionary | Recur | Memo | Leetcode 1639 | MIK • codestorywithMIK • 13,670 views views
Watch 9 more video solutions →Practice Number of Ways to Form a Target String Given a Dictionary with our built-in code editor and test cases.
Practice on FleetCode