aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-28 22:45:59 -0700
committerJack Sangdahl <[email protected]>2024-12-28 22:45:59 -0700
commit6ec780559494acbb28bb161e90963a9e0ce48bc2 (patch)
treef05e9c7c86320b5aac8b5d9be64493bbca862917
parent54c2ee3c2fdbddd44f8ebddd720234d9b0e36e5d (diff)
downloadleetcode-6ec780559494acbb28bb161e90963a9e0ce48bc2.tar.gz
leetcode-6ec780559494acbb28bb161e90963a9e0ce48bc2.zip
1639. number of ways to form a target string given a dictionary
-rw-r--r--num_ways_dict.c25
-rw-r--r--num_ways_dict.cpp40
-rw-r--r--num_ways_dict.py32
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"))