2023.04.16 Today's Challenge

https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/

Number of Ways to Form a Target String Given a Dictionary - LeetCode

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        ab = 26
        mod = 1000000007
        m, k = len(target), len(words[0])
        cnt = [[0] * k for _ in range(ab)]

        for j in range(k):
            for word in words:
                cnt[ord(word[j]) - ord('a')][j] += 1
        
        dp = [[0] * (k+1) for _ in range(m+1)]
        dp[0][0] = 1

        for i in range(m+1):
            for j in range(k):
                if i < m:
                    dp[i+1][j+1] += (cnt[ord(target[i]) - ord('a')][j] * dp[i][j])
                    dp[i+1][j+1] %= mod
                
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
        
        return dp[m][k]