Skip to main content
Talentd

Number of Ways to Form a Target String Given a Dictionary - Solution & Explanation

HardArrayStringDynamic Programming31 min readAsked at: Amazon, Meta, Uber +6
Practice this problem

Problem Statement

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.
  • To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].
  • Once you use the 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.
  • Repeat the process until you form the 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 <= 1000
  • 1 <= words[i].length <= 1000
  • All strings in words have the same length.
  • 1 <= target.length <= 1000
  • words[i] and target contain only lowercase English letters.

Approach Overview

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.

Approach 1: Dynamic Programming with Character Frequency Table

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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).

Try this approach in the editor →

Approach 2: Memoization Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).

Try this approach in the editor →

Approach 3: Preprocessing + Memory Search

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:

  • If i geq m, it means that all characters in target have been selected, then the number of schemes is 1.
  • If j geq n, it means that all characters in words have been selected, then the number of schemes is 0.
  • Otherwise, we can choose not to select the character in the 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Preprocessing + Dynamic Programming

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m*t).

Memoization Approach

Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).

Preprocessing + Memory Search—
Preprocessing + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Memoization with Recursive ChoicesO(n*m + m*t)O(m*t)When deriving the recurrence or explaining the DP state during interviews
Dynamic Programming with Character Frequency TableO(n*m + m*t)O(t)Optimal solution for large inputs and production-quality implementations

Video Solution

Number of Ways to Form a Target String Given a Dictionary | Recur | Memo | Leetcode 1639 | MIK • codestorywithMIK • 14,892 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Form a Target String Given a Dictionary easy or hard?
The problem is classified as Hard on LeetCode because it combines preprocessing, dynamic programming, and combinatorial counting. Recognizing that columns can be reused across different words but must follow strict order is the key challenge.
Number of Ways to Form a Target String Given a Dictionary Python/Java solution
Python and Java implementations typically build a 2D frequency array for characters and then run a DP loop over the target length. Python often uses a list for dp with modulo arithmetic, while Java uses long arrays to handle large counts before applying the modulo constraint.
How to solve Number of Ways to Form a Target String Given a Dictionary in O(n*m + m*t)?
Precompute a frequency table that stores how many words contain each character at every column. Then maintain a DP array where dp[i] represents the number of ways to build the first i characters of the target. Iterate columns from left to right and update the DP array backward using the stored frequencies.
What is the best approach for Number of Ways to Form a Target String Given a Dictionary?
The best approach uses dynamic programming with a character frequency table. First count how many times each character appears in every column of the dictionary, then run DP over the target string while iterating through columns. This reduces the complexity to O(n*m + m*t), where n is the number of words, m is the word length, and t is the target length.
Is Number of Ways to Form a Target String Given a Dictionary asked at Google/Amazon/Meta?
Dynamic programming string construction problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants involving counting subsequences, column constraints, or DP with preprocessing are common in high-level coding rounds.
What data structure is used in Number of Ways to Form a Target String Given a Dictionary?
The solution primarily uses arrays for the character frequency table and dynamic programming states. The frequency table stores counts of characters per column, while the DP array tracks how many ways each prefix of the target can be formed.
What is the time complexity of Number of Ways to Form a Target String Given a Dictionary?
The optimal solution runs in O(n*m + m*t) time. O(n*m) is used to build the column frequency table from the dictionary, and O(m*t) is used for the dynamic programming transitions that count ways to form prefixes of the target.

Ready to solve this problem?

Practice Number of Ways to Form a Target String Given a Dictionary with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays