Number of Ways to Form a Target String Given a Dictionary solution and explanation
Google
9 more videos on this problem
Number of Ways to Form a Target String Given a Dictionary | Recur | Memo | Leetcode 1639 | MIKcodestorywithMIK · 29:15 · 14K views
Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - PythonNeetCodeIO · 17:19 · 13K views
Number of Ways to Form a Target String Given a Dictionary | Bottom Up | Leetcode 1639 | MIKcodestorywithMIK · 17:56 · 6K views
1639. Number of Ways to Form a Target String Given a Dictionary || Dynamic ProgrammingAryan Mittal · 23:41 · 4K views
LeetCode 1639. Number of Ways to Form a Target String Given a DictionaryHappy Coding · 18:26 · 4K views
Number of Ways to Form a Target String Given a Dictionary | Leetcode 1639Techdose · 29:12 · 3K views
1639. Number of Ways to Form a Target String Given a Dictionary | LeetCode Daily Challenge | POTDDeep Tech · 14:06 · 2K views
1639. (Hard) Number of Ways to Form a Target String Given a Dictionary - Daily Leetcode (Day 75)yeetcode · 15:00 · 1K views
1639. Number of Ways to Form a Target String Given a Dictionary (Leetcode Hard)Programming Live with Larry · 20:13 · 1K views
Leetcode 1639. Number of Ways to Form a Target String Given a DictionaryFraz · 11:08 · 850 views
The problem
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:
targetshould be formed from left to right.- To form the
ithcharacter (0-indexed) oftarget, you can choose thekthcharacter of thejthstring inwordsiftarget[i] = words[j][k]. - Once you use the
kthcharacter of thejthstring ofwords, you can no longer use thexthcharacter of any string inwordswherex <= k. In other words, all characters to the left of or at indexkbecome 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 <= 10001 <= words[i].length <= 1000- All strings in
wordshave the same length. 1 <= target.length <= 1000words[i]andtargetcontain 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.
def numWays(words, target):
MOD = 10**9 + 7
m, t = len(words[0]), len(target)
dp = [[0] * (m + 1) for _ in range(t + 1)]
count = [[0] * 26 for _ in range(m)]
for word in words:
for i, char in enumerate(word):
count[i][ord(char) - ord('a')] += 1
for j in range(m + 1):
dp[0][j] = 1
for i in range(1, t + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i][j - 1]
if count[j - 1][ord(target[i - 1]) - ord('a')] > 0:
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * count[j - 1][ord(target[i - 1]) - ord('a')]) % MOD
return dp[t][m]class Solution {
public static final int MOD = 1000000007;
public int numWays(String[] words, String target) {
int m = words[0].length(), t = target.length();
int[][] dp = new int[t+1][m+1];
int[][] count = new int[m][26];
for (String word : words)
for (int i = 0; i < m; ++i)
count[i][word.charAt(i) - 'a']++;
for (int j = 0; j <= m; ++j)
dp[0][j] = 1;
for (int i = 1; i <= t; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = dp[i][j-1];
if (count[j-1][target.charAt(i-1) - 'a'] > 0)
dp[i][j] += (long)dp[i-1][j-1] * count[j-1][target.charAt(i-1) - 'a'] % MOD;
dp[i][j] %= MOD;
}
}
return dp[t][m];
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int numWays(vector<string>& words, string target) {
const int MOD = 1e9 + 7;
int m = words[0].size(), t = target.size();
vector<vector<int>> dp(t+1, vector<int>(m+1));
vector<vector<int>> count(m, vector<int>(26));
for (const string& word : words)
for (int i = 0; i < m; ++i)
++count[i][word[i] - 'a'];
dp[0][0] = 1;
for (int j = 0; j < m; ++j)
dp[0][j+1] = 1;
for (int i = 1; i <= t; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = dp[i][j-1];
if (count[j-1][target[i-1] - 'a'] > 0)
dp[i][j] = (dp[i][j] + (long long)dp[i-1][j-1] * count[j-1][target[i-1] - 'a']) % MOD;
}
}
return dp[t][m];
}
};var numWays = function(words, target) {
const MOD = 1e9 + 7;
const m = words[0].length, t = target.length;
const dp = Array.from({ length: t + 1 }, () => Array(m + 1).fill(0));
const count = Array.from({ length: m }, () => Array(26).fill(0));
for (let word of words) {
for (let i = 0; i < m; ++i) {
count[i][word.charCodeAt(i) - 'a'.charCodeAt(0)]++;
}
}
for (let j = 0; j <= m; ++j) {
dp[0][j] = 1;
}
for (let i = 1; i <= t; ++i) {
for (let j = 1; j <= m; ++j) {
dp[i][j] = dp[i][j - 1];
const charIndex = target.charCodeAt(i - 1) - 'a'.charCodeAt(0);
if (count[j - 1][charIndex] > 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * count[j - 1][charIndex]) % MOD;
}
}
}
return dp[t][m];
};#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int numWays(char **words, int wordsSize, char *target) {
int wordLen = strlen(words[0]);
int targetLen = strlen(target);
int dp[targetLen+1][wordLen+1];
int count[wordLen][26];
memset(count, 0, sizeof(count));
for (int i = 0; i < wordsSize; ++i) {
for (int j = 0; j < wordLen; ++j) {
count[j][words[i][j] - 'a']++;
}
}
for (int i = 0; i <= targetLen; +i++) {
dp[i][0] = i == 0 ? 1 : 0;
}
for (int j = 1; j <= wordLen; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i <= targetLen; ++i) {
for (int j = 1; j <= wordLen; ++j) {
dp[i][j] = dp[i][j-1];
int charIndex = target[i-1] - 'a';
dp[i][j] += (long long)dp[i-1][j-1] * count[j-1][charIndex] % MOD;
dp[i][j] %= MOD;
}
}
return dp[targetLen][wordLen];
}using System;
public class Solution {
private const int MOD = 1000000007;
public int NumWays(string[] words, string target) {
int m = words[0].Length, t = target.Length;
int[,] dp = new int[t+1, m+1];
int[,] count = new int[m, 26];
foreach (var word in words)
for (int i = 0; i < m; ++i)
count[i, word[i] - 'a']++;
for (int j = 0; j <= m; ++j)
dp[0, j] = 1;
for (int i = 1; i <= t; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i, j] = dp[i, j - 1];
if (count[j - 1, target[i - 1] - 'a'] > 0) {
dp[i, j] = (int)((dp[i, j] + (long)dp[i - 1, j - 1] *
count[j - 1, target[i - 1] - 'a']) % MOD);
}
}
}
return dp[t, m];
}
}This Python solution mirrors the dynamic programming approach from previous languages. It establishes a DP table to compute the number of ways to form subsequences of the target using columns of characters from words, relying on a frequency table to count possible contributions from each column. The results are accumulated and returned modular.
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).
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.
def numWays(words, target):
MOD = 10**9 + 7
m, t = len(words[0]), len(target)
dp = [[-1] * (m + 1) for _ in range(t + 1)]
count = [[0] * 26 for _ in range(m)]
for word in words:
for i, char in enumerate(word):
count[i][ord(char) - ord('a')] += 1
def dfs(i, j):
if i == t: return 1
if j == m: return 0
if dp[i][j] != -1: return dp[i][j]
res = dfs(i, j + 1)
if count[j][ord(target[i]) - ord('a')] > 0:
res = (res + count[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD
dp[i][j] = res
return dp[i][j]
return dfs(0, 0)import java.util.Arrays;
class Solution {
private static final int MOD = 1000000007;
private int[][] dp;
private int[][] count;
private int dfs(String target, int i, int j, int m) {
if (i == target.length()) return 1;
if (j == m) return 0;
if (dp[i][j] != -1) return dp[i][j];
int res = dfs(target, i, j + 1, m);
if (count[j][target.charAt(i) - 'a'] > 0) {
res = (int)((res + (long)count[j][target.charAt(i) - 'a'] * dfs(target, i + 1, j + 1, m)) % MOD);
}
return dp[i][j] = res;
}
public int numWays(String[] words, String target) {
int m = words[0].length();
dp = new int[target.length()][m];
for (int[] row : dp) Arrays.fill(row, -1);
count = new int[m][26];
for (String word : words)
for (int i = 0; i < m; ++i)
count[i][word.charAt(i) - 'a']++;
return dfs(target, 0, 0, m);
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
const int MOD = 1e9 + 7;
vector<vector<int>> dp;
vector<vector<int>> count;
int dfs(string &target, int i, int j, int m) {
if (i == target.size()) return 1;
if (j == m) return 0;
if (dp[i][j] != -1) return dp[i][j];
int res = dfs(target, i, j + 1, m);
if (count[j][target[i] - 'a'] > 0)
res = (res + (long long)count[j][target[i] - 'a'] * dfs(target, i + 1, j + 1, m) % MOD) % MOD;
return dp[i][j] = res;
}
int numWays(vector<string> &words, string target) {
int m = words[0].size();
dp = vector<vector<int>>(target.size(), vector<int>(m, -1));
count = vector<vector<int>>(m, vector<int>(26));
for (const string &word : words)
for (int i = 0; i < m; ++i)
count[i][word[i] - 'a']++;
return dfs(target, 0, 0, m);
}
};var numWays = function(words, target) {
const MOD = 1e9 + 7;
const m = words[0].length, t = target.length;
const dp = Array.from({ length: t + 1 }, () => Array(m + 1).fill(-1));
const count = Array.from({ length: m }, () => Array(26).fill(0));
for (let word of words) {
for (let i = 0; i < m; ++i) {
count[i][word.charCodeAt(i) - 'a'.charCodeAt(0)]++;
}
}
const dfs = (i, j) => {
if (i === t) return 1;
if (j === m) return 0;
if (dp[i][j] !== -1) return dp[i][j];
let res = dfs(i, j + 1);
const charIndex = target.charCodeAt(i) - 'a'.charCodeAt(0);
if (count[j][charIndex] > 0) {
res = (res + count[j][charIndex] * dfs(i + 1, j + 1)) % MOD;
}
dp[i][j] = res;
return res;
};
return dfs(0, 0);
};#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int dp[1001][1001];
int count[1001][26];
int dfs(char **words, int wordsSize, char *target, int i, int j, int wordLen) {
if (i == strlen(target)) return 1;
if (j == wordLen) return 0;
if (dp[i][j] != -1) return dp[i][j];
int res = dfs(words, wordsSize, target, i, j + 1, wordLen);
int charIndex = target[i] - 'a';
if (count[j][charIndex] > 0)
res = (res + (long long)count[j][charIndex] * dfs(words, wordsSize, target, i + 1, j + 1, wordLen) % MOD) % MOD;
return dp[i][j] = res;
}
int numWays(char **words, int wordsSize, char *target) {
int wordLen = strlen(words[0]);
memset(dp, -1, sizeof(dp));
memset(count, 0, sizeof(count));
for (int i = 0; i < wordsSize; ++i) {
for (int j = 0; j < wordLen; ++j) {
count[j][words[i][j] - 'a']++;
}
}
return dfs(words, wordsSize, target, 0, 0, wordLen);
}using System;
public class Solution {
private const int MOD = 1000000007;
private int[,] dp;
private int[,] count;
private int Dfs(string target, int i, int j, int m) {
if (i == target.Length) return 1;
if (j == m) return 0;
if (dp[i, j] != -1) return dp[i, j];
int res = Dfs(target, i, j + 1, m);
if (count[j, target[i] - 'a'] > 0) {
res = (int)((res + (long)count[j, target[i] - 'a'] * Dfs(target, i + 1, j + 1, m)) % MOD);
}
dp[i, j] = res;
return res;
}
public int NumWays(string[] words, string target) {
int m = words[0].Length;
dp = new int[target.Length, m + 1];
count = new int[m, 26];
Array.Fill(dp, -1);
foreach (var word in words)
for (int i = 0; i < m; ++i)
count[i, word[i] - 'a']++;
return Dfs(target, 0, 0, m);
}
}This Python solution applies memoization on top of a recursive depth-first search approach. By storing results in a memo array (`dp`), it prevents recalculated paths for `dfs(i, j)`, ensuring optimal performance without overlapping computations.
Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).
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 intargethave been selected, then the number of schemes is1. - If
j geq n, it means that all characters inwordshave been selected, then the number of schemes is0. - Otherwise, we can choose not to select the character in the
j-th position ofwords, then the number of schemes isdfs(i, j + 1); or we choose the character in thej-th position ofwords, then the number of schemes isdfs(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.
function numWays(words: string[], target: string): number {
const m = target.length;
const n = words[0].length;
const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
const mod = 1e9 + 7;
for (let j = 0; j <= n; ++j) {
f[0][j] = 1;
}
const cnt = new Array(n).fill(0).map(() => new Array(26).fill(0));
for (const w of words) {
for (let j = 0; j < n; ++j) {
++cnt[j][w.charCodeAt(j) - 97];
}
}
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
f[i][j] = f[i][j - 1] + f[i - 1][j - 1] * cnt[j - 1][target.charCodeAt(i - 1) - 97];
f[i][j] %= mod;
}
}
return f[m][n];
}func numWays(words []string, target string) int {
m, n := len(target), len(words[0])
f := make([][]int, m)
cnt := make([][26]int, n)
for _, w := range words {
for j, c := range w {
cnt[j][c-'a']++
}
}
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -1
}
}
const mod = 1e9 + 7
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= m {
return 1
}
if j >= n {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := dfs(i, j+1)
ans = (ans + dfs(i+1, j+1)*cnt[j][target[i]-'a']) % mod
f[i][j] = ans
return ans
}
return dfs(0, 0)
}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.
func numWays(words []string, target string) int {
const mod = 1e9 + 7
m, n := len(target), len(words[0])
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for j := range f[0] {
f[0][j] = 1
}
cnt := make([][26]int, n)
for _, w := range words {
for j, c := range w {
cnt[j][c-'a']++
}
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
f[i][j] = f[i][j-1] + f[i-1][j-1]*cnt[j-1][target[i-1]-'a']
f[i][j] %= mod
}
}
return f[m][n]
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.