## Problem

**Problem ID**: 1744

**Title**: Number of Ways to Form a Target String Given a Dictionary

**Difficulty**: Hard

**Description**:

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
`i`

character (^{th}**0-indexed**) of`target`

, you can choose the`k`

character of the^{th}`j`

string in^{th}`words`

if`target[i] = words[j][k]`

. - Once you use the
`k`

character of the^{th}`j`

string of^{th}`words`

, you**can no longer**use the`x`

character of any string in^{th}`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**

`10`^{9} + 7

.

**Example 1:**

Input:words = ["acca","bbbb","caca"], target = "aba"Output:6Explanation: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:4Explanation: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.

## Thoughts

I found this problem very hard. Took around and hour to solve the problem. It is quite obvious that this is a DP problem as it involves counting. However, I was initially tricked into thinking that DP state involves the word index.

I could quickly develop the correct DP state and DP transition but I found huge difficulty optimising it from a O(N^3) solution to a O(N^2) solution.

My solution led to flaky TLE but eventhough the time complexity is exactly the same as the model answer solution in the discuss.

## Solution

**General Idea**

For each characters in the target, find the possible indexes it can match to in
the `words`

. This simplifies the problem to finding the number of ways to
select the associated indexes for each character in the target such that the
indexes are increasing. This could solved using DP.

DP State | `dp[i][j]`

: represents the total number of ways to match `target[0,...,i]`

characters
with the first `words[k][0,...,j]`

characters (for all `k`

).

DP Transition:

- Do not use the
`j`

th character of`words`

to match`target[i]`

.- Instead Use the
`j<`

th character of`words`

to match`target[i]`

`dp[i][j] += dp[i][j-1]`

- Instead Use the
- Use the
`j`

th character of`words`

to match`target[i]`

- For each instance of
`j`

th character of`words`

that matches`target[i]`

, extend it from the previously calculated ways for the`j <`

th character of`words`

to match`target[0,..., i-1]`

`dp[i][j] += dp[i-1][j-1]*freq`

- For each instance of

### Implementation

```
class Solution {
public:
int numWays(vector<string>& words, string target) {
unordered_set<char> target_chars(target.begin(), target.end());
unordered_map<char, map<int,int> > char_idxes;
auto m = size_t{0};
for (const auto& word : words) {
m = max(m, word.size());
for (size_t i = 0; i < word.size(); i++) {
if (target_chars.count(word[i]) == 0) continue;
char_idxes[word[i]][i] += 1;
}
}
auto n = target.size();
vector<vector<int>> dp(n, vector<int>(m));
auto print = [&dp, &char_idxes]() {
cout << "Char Index" << endl;
for (auto& [c, m] : char_idxes) {
cout << c << endl;
for(auto& [i, frq] : m) {
cout << " " << i << "*" << frq << endl;
}
}
cout << "DP" << endl;
for (const auto& row : dp) {
for (const auto i : row) cout << i << " ";
cout << endl;
}
};
for (auto [j, freq] : char_idxes[target[0]]) dp[0][j] += freq;
for (int j = 1; j < m; j++) dp[0][j] += dp[0][j-1];
m = char_idxes[target.back()].rbegin()->first;
for (int i = 1; i < n; i++) {
char target_c = target[i];
for (int j = 1; j <= m; j++) {
int freq = char_idxes[target_c].count(j) ? char_idxes[target_c][j] : 0;
if (freq > 0) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % static_cast<int>(1e9+7);
int tmp = 0;
for (int k = 0; k < freq; k++) {
tmp = (tmp + dp[i][j])%static_cast<int>(1e9+7);
}
dp[i][j] = tmp;
dp[i][j] = (dp[i][j] + dp[i][j-1]) % static_cast<int>(1e9+7); // dont select the current char
}
}
return dp[n-1][m];
}
};
```