Number of Ways to Form a Target String Given a Dictionary LeetCode solution in Python

1
class Solution:
2
    def numWays(self, words: List[str], target: str) -> int:
3
        MOD = 10**9 + 7
4
        m, n = len(words[0]), len(target)
5
        charAtIndexCnt = [[0] * m for _ in range(128)]
6
        for word in words:
7
            for i, c in enumerate(word):
8
                charAtIndexCnt[ord(c)][
9
                    i
10
                ] += 1  # Count the number of character `c` at index `i` of all words
11

12
        @lru_cache(None)
13
        def dp(k, i):
14
            if i == n:  # Formed a valid target
15
                return 1
16
            if k == m:  # Reached to length of words[x] but don't found any result
17
                return 0
18
            c = target[i]
19
            ans = dp(k + 1, i)  # Skip k_th index of words
20
            if (
21
                charAtIndexCnt[ord(c)][k] > 0
22
            ):  # Take k_th index of words if found character `c` at index k_th
23
                ans += dp(k + 1, i + 1) * charAtIndexCnt[ord(c)][k]
24
                ans %= MOD
25
            return ans
26

27
        return dp(0, 0)