1639. Number of Ways to Form a Target String Given a Dictionary
Problem Description
In this problem, you are given a list of strings called words
, where each string is of the same length, and a target string target
. Your goal is to construct the target string character by character, from left to right, using characters from the strings in words
. The key rules to follow while forming the target string are:
- You may select the character at position
k
from thej
th string inwords
to form thei
th character oftarget
, if and only iftarget[i]
matcheswords[j][k]
. - After using the
k
th character fromj
th string ofwords
, all characters at or to the left of positionk
in any string ofwords
can no longer be used. This means you have to choose subsequent characters from positions greater thank
. - You can repeat this process of selecting characters from
words
until you completely form thetarget
string. - It is allowed to use multiple characters from the same string in
words
as long as they meet the above conditions.
The problem asks for the number of distinct ways to form the target
from words
. As the total number could be very large, you are required to return this number modulo 10^9 + 7
.
Intuition
To solve this problem, we make use of dynamic programming or a depth-first search approach to count all possible ways to construct the target
.
Firstly, we process the words
array to calculate the frequency of each character at each position (count array cnt
). This preprocessing step simplifies the dynamic programming or DFS implementation by giving quick access to the number of times a particular character appears in each position across all strings.
The next step is defining a recursive function, let's call it dfs(i, j)
, representing the number of ways to construct the substring of target
starting at index i
with the starting character position in words
being j
. Our base cases are when we've successfully formed the target
string (all characters are chosen) or when we can no longer choose characters from words
(out of bounds).
The transitions depend on our choices at each step:
- We can decide not to pick a character at position
j
in any string ofwords
, in which case we simply move to the next character position inwords
(dfs(i, j + 1)
). - Alternatively, we can pick the character if it matches the current target character we want to form, and then move to the next character in both target and words, while also multiplying by the count of the selected character (
dfs(i + 1, j + 1) * count
).
Finally, we initiate our search/recursion from the beginning of the target
string and the words
array (dfs(0, 0)
), and continuously add the number of ways at each new choice we can make.
In the case of dynamic programming, we employ a bottom-up approach to store and reuse the results of subproblems, using a 2D table f[i][j]
to represent the number of ways to build up to the ith
character of target
considering characters upto jth
position in the strings of words
.
Overall, the problem is approached via breaking down the complex task of string construction into smaller subproblems, calculating the number of ways for each subproblem, and then using these to build up to the final solution.
Learn more about Dynamic Programming patterns.
Solution Approach
The problem lends itself nicely to a depth-first search (DFS) with memoization or dynamic programming to avoid redundant computations. In both the recursive (DFS) and iterative (dynamic programming) approach, a crucial step is preprocessing, and an essential data structure used is the count array cnt
.
Preprocessing
Before we dive into building the target
string, we calculate the frequency of each character at every position across all strings in words
. We create a 2D array cnt
of size n Ć 26
, where n
is the length of the strings in words
. cnt[j][c]
keeps track of how many times the character c
appears in the j
th position in all strings of words
.
Recursive DFS with Memoization
In the DFS approach, we define a function dfs(i, j)
that computes the number of ways to construct substring target[i...]
given that we are currently looking to match characters starting from position j
in the strings of words
.
The recursion has two base cases:
- When
i >= m
, which means the entiretarget
is formed, the number of ways is1
. - When
j >= n
, which implies we can't select more characters fromwords
and haven't formed thetarget
, the number of ways is0
.
For other cases, we have two choices:
- We can opt not to choose a character from position
j
inwords
, so we explore further withdfs(i, j + 1)
. - If we pick the character, we use the count of that character at position
j
and proceed to the next characters in bothtarget
andwords
(dfs(i + 1, j + 1) * cnt[j][target[i] - 'a']
).
The results of these calls are added together to get the final answer for dfs(i, j)
and memoized to optimize overlapping subproblems. The modulo operation ensures the answer does not overflow the limits.
Dynamic Programming
In dynamic programming, we also take advantage of the count array cnt
. The dp array f[i][j]
represents the number of ways to construct the first i
characters of target
while restricted to using up to the first j
characters from each string in words
.
We initialize f[0][j] = 1
for all 0 ā¤ j ā¤ n
because there's always one way to construct an empty target regardless of words
.
The dp transitions are straightforward: for each cell f[i][j]
, we consider two cases:
- Not selecting the
j
-th character fromwords
: we just carry over the previous countf[i][j - 1]
. - Selecting the
j
-th character: the number of ways increases by the number of ways to make the prefixtarget[...i - 1]
while considering characters only up toj - 1
th position multiplied by the count of thetarget[i - 1]
at this positioncnt[j - 1][target[i - 1] - 'a']
.
The total number of ways for f[i][j]
is the sum of the counts from the two cases, and we must again apply the modulo here. Once all cells are calculated, f[m][n]
will contain the answer.
Both recursive and dynamic programming solutions ensure that we do not perform the same calculations repeatedly, and both require O(m * n)
time and space, where m
is the length of the target and n
is the length of the strings in words
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach described.
Suppose we have the following inputs:
words = ["ax", "by", "cz"]
target = "abc"
Our target
is "abc"
, and our words
list contains strings of the same length, i.e., 2.
Preprocessing Step
Firstly, we create the count array cnt
from words
. Since all strings in words
are of length 2, we will have a 2 by 26 (number of letters in the alphabet) count matrix.
cnt
would be as follows:
- For the first position (index
0
) in our strings:a
appears once (in "ax"),b
appears once (in "by"),c
appears once (in "cz").
- For the second position (index
1
) in our strings:x
,y
, andz
each appear once.
Our cnt
array after processing:
cnt[0][0] = 1 // 'a' at position 0 cnt[0][1] = 1 // 'b' at position 0 cnt[0][2] = 1 // 'c' at position 0 ... // other letters at position 0 would be 0 cnt[1][23] = 1 // 'x' at position 1 cnt[1][24] = 1 // 'y' at position 1 cnt[1][25] = 1 // 'z' at position 1 ... // other letters at position 1 would be 0
Recursive DFS with Memoization
We define our dfs
function to begin constructing the target
.
For target[0] = 'a'
, the DFS explores:
dfs(1, 1)
since 'a' can be chosen fromwords[0] = "ax"
at position0
. The count iscnt[0][0] = 1
.
Next, for target[1] = 'b'
, from the new starting point j = 1
, the DFS finds:
dfs(2, 2)
this time choosing 'b' fromwords[1] = "by"
at position1
(since 'b' doesn't appear at position1
in "ax"). The count iscnt[1][1] = 1
.
Finally, for target[2] = 'c'
:
- We would choose 'c' from
words[2] = "cz"
at position2
, which again has a count ofcnt[2][2] = 1
.
Since each step gives us a count of 1
, and we can form the target with one way at each step, the DFS would end with a total of 1
way to create the target "abc".
Dynamic Programming
Using dynamic programming, we construct a DP table f
that has m
rows (target length + 1) and n
columns (words string length + 1).
The base case is f[0][j] = 1
for all j
, indicating that there is one way to construct an empty target.
The table is filled according to the discussed transitions. By examining choices at each step, the DP table for our example would look like:
f[0][0] = 1 f[0][1] = 1 f[0][2] = 1 From the transitions, we would find: f[1][1] = f[0][0] * cnt[0]['a' - 'a'] = 1 f[1][2] = f[1][1] = 1 f[2][2] = f[1][1] * cnt[1]['b' - 'a'] = 1
Since f[2][2]
gives the number of ways to form "ab"
using up to the second position in strings of words
and cnt[2]['c' - 'a'] = 1
, the final count f[3][3]
for forming the entire "abc"
target will be f[2][2] * cnt[2]['c' - 'a'] = 1 * 1 = 1
.
Hence, there is 1
distinct way to form target = "abc"
using the strings in words
. This result matches our DFS calculation.
Solution Implementation
1from typing import List
2from functools import lru_cache
3
4class Solution:
5 def numWays(self, words: List[str], target: str) -> int:
6 # Define a dynamic programming function with memoization using LRU (Least Recently Used) cache
7 @lru_cache(maxsize=None)
8 def dfs(target_index: int, word_index: int) -> int:
9 # Base case: if all characters of the target are matched, return 1
10 if target_index >= target_length:
11 return 1
12 # Base case: if end of the words character columns are reached, return 0
13 if word_index >= num_columns:
14 return 0
15 # Count the ways if including the current character from the target
16 count_including = dfs(target_index + 1, word_index + 1) * char_frequency[word_index][ord(target[target_index]) - ord('a')]
17 # Count the ways if not including the current character from the target
18 count_excluding = dfs(target_index, word_index + 1)
19 # Add the ways from including and excluding the current character and take modulo
20 answer = (count_including + count_excluding) % modulo
21
22 return answer
23
24 # Calculate the length of target and the number of columns from the first word (all words have the same length by assumption)
25 target_length = len(target)
26 num_columns = len(words[0])
27 modulo = 10**9 + 7 # Define the modulo constant
28
29 # Initialize character frequency matrix with 26 columns for each alphabet character and rows equalling the number of columns in words
30 char_frequency = [[0] * 26 for _ in range(num_columns)]
31 # Fill the character frequency matrix with the frequency of each character at each column in the words
32 for word in words:
33 for column_index, char in enumerate(word):
34 char_frequency[column_index][ord(char) - ord('a')] += 1
35
36 # Start the DFS traversal with the first character of the target and the first column of the words
37 return dfs(0, 0)
38
1class Solution {
2 private int targetLength; // Length of the target string
3 private int wordLength; // Length of the words
4 private String target; // The target string
5 private Integer[][] memo; // Memoization array
6 private int[][] charCount; // Counts of each character at each position across all words
7 private final int MOD = (int) 1e9 + 7; // The modulus value for avoiding overflow
8
9 public int numWays(String[] words, String target) {
10 targetLength = target.length();
11 wordLength = words[0].length();
12 memo = new Integer[targetLength][wordLength];
13 this.target = target;
14 charCount = new int[wordLength][26]; // 26 for 'a' to 'z'
15
16 // Count the occurrence of each character in each column
17 for (String word : words) {
18 for (int j = 0; j < wordLength; ++j) {
19 charCount[j][word.charAt(j) - 'a']++;
20 }
21 }
22
23 // Start the depth-first search from the first character of target
24 // and first character position in words
25 return dfs(0, 0);
26 }
27
28 private int dfs(int i, int j) {
29 // If we have matched all characters of target return 1 way to match
30 if (i >= targetLength) {
31 return 1;
32 }
33 // If we run out of positions in words before matching target, return 0 ways
34 if (j >= wordLength) {
35 return 0;
36 }
37 // If we have already computed this state, return its value
38 if (memo[i][j] != null) {
39 return memo[i][j];
40 }
41
42 // Case 1: Skip the current position in words and move to the next
43 long ans = dfs(i, j + 1);
44
45 // Case 2: Use the current position in words if it matches the current character in target
46 ans += (long) dfs(i + 1, j + 1) * charCount[j][target.charAt(i) - 'a'];
47
48 // Modulus operation to avoid integer overflow
49 ans %= MOD;
50
51 // Save and return the computed value
52 return memo[i][j] = (int) ans;
53 }
54}
55
1// Class to solve the problem of counting the number of ways to form a target string from a vertical sequence of characters in a list of strings
2class Solution {
3public:
4 int numWays(vector<string>& words, string target) {
5 const int MOD = 1e9 + 7; // Define the modulus to keep the numbers within the integer limit
6 int targetLength = target.size(), wordLength = words[0].size(); // Size of the target string and length of each word in the array
7 vector<vector<int>> count(wordLength, vector<int>(26)); // 2D vector to store the count of each character at each position
8
9 // Loop to count the frequency of each character at each column in the word list
10 for (auto& word : words) {
11 for (int j = 0; j < wordLength; ++j) {
12 ++count[j][word[j] - 'a']; // Increment the count of the character at the relevant position
13 }
14 }
15
16 // DP array initialized with -1 to indicate that the value hasn't been computed yet
17 int dp[targetLength][wordLength];
18 memset(dp, -1, sizeof(dp));
19
20 // Recursive lambda function to compute the number of ways using Depth First Search (DFS)
21 function<int(int, int)> dfs = [&](int i, int j) -> int {
22 if (i >= targetLength) {
23 return 1; // If the whole target is found, return 1 way
24 }
25 if (j >= wordLength) {
26 return 0; // If the end of the word is reached, no more ways can be found, return 0
27 }
28 if (dp[i][j] != -1) {
29 return dp[i][j]; // If the value is already computed, return the cached result
30 }
31 int ways = dfs(i, j + 1); // Recursive call to check for ways without using the current position
32 ways = (ways + 1LL * dfs(i + 1, j + 1) * count[j][target[i] - 'a']) % MOD; // Add the ways using the current character and proceed
33 return dp[i][j] = ways; // Store the computed ways in the DP array for memoization
34 };
35
36 // Call the DFS function starting from the first character of the target and the word
37 return dfs(0, 0);
38 }
39};
40
1function numWays(words: string[], target: string): number {
2 // m is the length of the target string.
3 const targetLength = target.length;
4 // n is the length of the words assuming all words have the same length.
5 const wordLength = words[0].length;
6 // f is the dynamic programming table with dimensions (targetLength+1) x (wordLength+1).
7 const dp = new Array(targetLength + 1).fill(0).map(() => new Array(wordLength + 1).fill(0));
8 // mod is the value for modulo operation to avoid integer overflow.
9 const MOD = 1e9 + 7;
10
11 // Initialize the first row of the dp table to 1s.
12 for (let j = 0; j <= wordLength; ++j) {
13 dp[0][j] = 1;
14 }
15
16 // cnt is a 2D array that holds the counts of each character at each position in words.
17 const charCount = new Array(wordLength).fill(0).map(() => new Array(26).fill(0));
18
19 // Populate charCount with the frequency of each character at each position.
20 for (const word of words) {
21 for (let j = 0; j < wordLength; ++j) {
22 ++charCount[j][word.charCodeAt(j) - 'a'.charCodeAt(0)];
23 }
24 }
25
26 // Build the dp table using the character frequencies.
27 for (let i = 1; i <= targetLength; ++i) {
28 for (let j = 1; j <= wordLength; ++j) {
29 dp[i][j] = (
30 dp[i][j - 1] + dp[i - 1][j - 1] * charCount[j - 1][target.charCodeAt(i - 1) - 'a'.charCodeAt(0)]
31 ) % MOD;
32 }
33 }
34
35 // The bottom-right cell of the dp table contains the number of ways to form the target.
36 return dp[targetLength][wordLength];
37}
38
Time and Space Complexity
The time complexity of the given code is O(m * n * k)
, where m
is the length of the target
string, n
is the length of the strings in the words
array, and k
is the number of recursive calls made, which does not exceed the length of the target string. Each function call iterates through the length of words[0]
, and there are m
possible values for i
and n
possible values for j
. The memoization through @cache
ensures that each (i, j)
pair's computation is done only once.
The space complexity is O(m * n)
for the memoization cache, which stores a result for each pair (i, j)
. Since there are m
possible values for i
and n
possible values for j
, we have m * n
pairs. Additionally, the cnt
array uses O(n * 26)
space, which simplifies to O(n)
since 26
is a constant. As a result, the space complexity does not change due to the cnt
array. The overall space complexity includes the stack space used by recursion calls, which could be O(m)
in the worst case. Hence, the total space complexity is O(m * n)
when considering the memoization and recursion stack space, where n
is the number of indices in each word and m
is the number of characters in the target
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!