aboutsummaryrefslogtreecommitdiff
path: root/num_ways_dict.py
diff options
context:
space:
mode:
Diffstat (limited to 'num_ways_dict.py')
-rw-r--r--num_ways_dict.py32
1 files changed, 32 insertions, 0 deletions
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"))