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

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 jth 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]
• Use the jth character of words to match target[i]
  • For each instance of jth 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

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];
    }
};