Number of Ways to Form a Target String Given a Dictionary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        n = len(target)
        MOD = int(1e9) + 7
        res = [0] * (n + 1)
        res[0] = 1

        for i in range(len(words[0])):
            count = [0] * 26
            for w in words:
                count[ord(w[i]) - ord('a')] += 1
            for j in range(n - 1, -1, -1):
                res[j + 1] += res[j] * count[ord(target[j]) - ord('a')] % MOD

        return int(res[n] % MOD)