aboutsummaryrefslogtreecommitdiff
path: root/other/num_ways_dict.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/num_ways_dict.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/num_ways_dict.cpp')
-rw-r--r--other/num_ways_dict.cpp35
1 files changed, 35 insertions, 0 deletions
diff --git a/other/num_ways_dict.cpp b/other/num_ways_dict.cpp
new file mode 100644
index 0000000..582c2f9
--- /dev/null
+++ b/other/num_ways_dict.cpp
@@ -0,0 +1,35 @@
+// 1639. Number of Ways to Form a Target String Given a Dictionary
+#include "leetcode.h"
+
+/*
+ * 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) {
+ 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;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<string> s1 = {"acca", "bbbb", "caca"}, s2 = {"abba", "baab"};
+ string t1 = "aba", t2 = "bab";
+ printf("%d\n", obj.numWays(s1, t1)); // expect: 6
+ printf("%d\n", obj.numWays(s2, t2)); // expect: 4
+}