diff options
Diffstat (limited to 'num_ways_dict.cpp')
-rw-r--r-- | num_ways_dict.cpp | 40 |
1 files changed, 19 insertions, 21 deletions
diff --git a/num_ways_dict.cpp b/num_ways_dict.cpp index f047326..582c2f9 100644 --- a/num_ways_dict.cpp +++ b/num_ways_dict.cpp @@ -1,30 +1,28 @@ // 1639. Number of Ways to Form a Target String Given a Dictionary #include "leetcode.h" -class Solution { - int dp[1001][1001] = {}; - int dfs(vvd(int) cnt, string target, int i, int j) { - if (j >= target.size()) - return 1; - if (!dp[i][j]) { - dp[i][j] = 1; - for (int k = i; k + (target.size() - j) <= cnt.size(); ++k) - if (cnt[k][target[j] - 'a']) - dp[i][j] = - ((long)cnt[k][target[j] - 'a'] * dfs(cnt, target, k + 1, j + 1) + - dp[i][j]) % - 1000000007; - } - return dp[i][j] - 1; - } +/* + * 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'. 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 from 'target' from + * 'words'. since the answer may be too large, return it modulo 10^9+7 + */ +class Solution { public: int numWays(vector<string> &words, string target) { - vvd(int) cnt(words[0].size(), vector<int>(26)); - for (auto w : words) - for (auto i = 0; i < w.size(); ++i) - ++cnt[i][w[i] - 'a']; - return dfs(cnt, target, 0, 0); + int n = target.length(), mod = 1e9 + 7; + vector<long> ans(n + 1); + ans[0] = 1; + for (int i = 0; i < words[0].length(); ++i) { + vector<int> cnt(26); + for (auto &w : words) + cnt[w[i] - 'a']++; + for (int j = n - 1; j >= 0; --j) + ans[j + 1] += ans[j] * cnt[target[j] - 'a'] % mod; + } + return ans[n] % mod; } }; |