https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/ from dunzo

Thinking process:

Check the constraint first. Looks like we need to do this in O(n^2) time.

It will be eaiser to look at an example. Let’s say words = ["acca","bbbb","caca"], target = "aba". We can define dp[i][j] to be the solution at ith char in target (starting from 1) and jth position in words like below.

// i=2
ab
// j=3
acc
bbb
cac

Here, we can see that the solution involes two cases: we either use 3rd char in words to form the solution or we don’t use 3rd char in words to form the solution. In first case, it’s like

 a b
ac c
bb b
ca c

So, our solution will be dp[i-1][j-1] * (number of b in words[_][j]). In this case, it’s 2*1 because there is only 1 b at position 3 (starting from 1) in words, and we can find two a from position 1~2.

The second case is something like below, which is 1 in this case (use a in words[0] and b in words[1])

ab

ac
bb
ca

So, the equation becomes

dp[i][j] = dp[i-1][j-1]*(number of target[i] in words at position j) + dp[i][j-1]

For the (number of target[i] in words at position j), we just need a little bit preprocess. We also need to initialize dp[0][x] = 1 as the answer is always 1 when target is an empty string (pick nothing in words then we can form the target).

Below is the code.

 1class Solution {
 2public:
 3    typedef long long ll;
 4    int numWays(vector<string>& words, string target) {
 5        int N = words[0].size();
 6        vector<vector<int>> cnt(26, vector<int>(N));
 7        for (auto w : words) {
 8            for (int i=0; i<N; i++) {
 9                cnt[w[i]-'a'][i]++;
10            }
11        }
12        int T = target.size();
13        int MOD = 1e9 + 7;
14        vector<vector<ll>> dp(T+1, vector<ll>(N+1));
15        for (int i=0; i<=N; i++) dp[0][i] = 1;
16        
17        for (int i=1; i<=T; i++) {
18            for (int j=1; j<=N; j++) {
19                dp[i][j] = dp[i-1][j-1]*cnt[target[i-1]-'a'][j-1] + dp[i][j-1];
20                dp[i][j] %= MOD;
21                if (dp[i][j] < 0) dp[i][j] += MOD;
22            }
23        }
24        return dp[T][N];
25    }
26};