diff options
author | Jack Sangdahl <[email protected]> | 2024-12-28 22:45:59 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-28 22:45:59 -0700 |
commit | 6ec780559494acbb28bb161e90963a9e0ce48bc2 (patch) | |
tree | f05e9c7c86320b5aac8b5d9be64493bbca862917 | |
parent | 54c2ee3c2fdbddd44f8ebddd720234d9b0e36e5d (diff) | |
download | leetcode-6ec780559494acbb28bb161e90963a9e0ce48bc2.tar.gz leetcode-6ec780559494acbb28bb161e90963a9e0ce48bc2.zip |
1639. number of ways to form a target string given a dictionary
-rw-r--r-- | num_ways_dict.c | 25 | ||||
-rw-r--r-- | num_ways_dict.cpp | 40 | ||||
-rw-r--r-- | num_ways_dict.py | 32 |
3 files changed, 66 insertions, 31 deletions
diff --git a/num_ways_dict.c b/num_ways_dict.c index cb712d0..ba60c39 100644 --- a/num_ways_dict.c +++ b/num_ways_dict.c @@ -1,11 +1,16 @@ // 1639. Number of Ways to Form a Target String Given a Dictionary -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +#include "leetcode.h" -#define MOD 1000000007 +/* + * 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 + */ int numWays(char **words, int words_size, char *target) { + const int mod = 1e9 + 7; int t_len = strlen(target), w_len = strlen(words[0]); long *ans = (long *)calloc(t_len + 1, sizeof(long)); ans[0] = 1; @@ -14,14 +19,14 @@ int numWays(char **words, int words_size, char *target) { for (int j = 0; j < words_size; j++) cnt[words[i][j] - 'a']++; for (int j = t_len - 1; j >= 0; j--) - ans[j + 1] += ans[j] * cnt[target[j] - 'a'] % MOD; + ans[j + 1] += ans[j] * cnt[target[j] - 'a'] % mod; } - return ans[t_len] % MOD; + return ans[t_len] % mod; } int main() { - char w1[][] = {{"acca"}, {"bbbb"}, {"caca"}}, t1[] = {"aba"}; - char w2[][] = {{"abba"}, {"baab"}}, t2[] = {"bab"}; - printf("%d\n", numWays(w1, 3, t1)); // expect: 6 - printf("%d\n", numWays(w2, 2, t2)); // expect: 6 + char *w1[] = {"acca", "bbbb", "caca"}, *t1 = "aba"; + char *w2[] = {"abba", "baab"}, *t2 = "bab"; + printf("%d\n", numWays((char **)w1, ARRAY_SIZE(w1), t1)); // expect: 6 + printf("%d\n", numWays((char **)w2, ARRAY_SIZE(w2), t2)); // expect: 4 } 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; } }; diff --git a/num_ways_dict.py b/num_ways_dict.py new file mode 100644 index 0000000..2c4d19e --- /dev/null +++ b/num_ways_dict.py @@ -0,0 +1,32 @@ +# 1639. Number of Ways to Form a Target String Given a Dictionary +from collections import Counter + +""" +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(object): + def numWays(self, words, target): + """ + :type words: List[str] + :type target: str + :rtype: int + """ + n, mod = len(target), 10**9 + 7 + ans = [1] + [0] * n + for i in range(len(words[0])): + cnt = Counter(w[i] for w in words) + for j in range(n - 1, -1, -1): + ans[j + 1] += ans[j] * cnt[target[j]] % mod + return ans[n] % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.numWays(words=["acca", "bbbb", "caca"], target="aba")) + print(obj.numWays(words=["abba", "baab"], target="bab")) |