23.04.16 Today’s Leetcode

1639. Number of Ways to Form a Target String Given a Dictionary

TLE at 76 / 89 testcases passed

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        d = defaultdict(list)
        for index, word in enumerate(words):
            for k, char in enumerate(word):
                d[char].append((index, k))
        # print(d)

        dp = {}
        
        @functools.lru_cache(None)
        def dfs(cur, index):
            if index == len(target):
                return 1
            if (cur, index) in dp:
                return dp[(cur, index)]
            res = 0
            for pair in d[target[index]]:
                if pair[1] > cur:
                    res += dfs(pair[1], index + 1)
            dp[(cur, index)] = res
            return res

        return dfs(-1, 0) % (10**9 + 7)

Top-down DP Approach

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        n = len(words[0])
        m = len(target)
        mod = 10 ** 9 + 7
        dp = [0] * (m + 1)
        dp[0] = 1
        
        count = [[0] * 26 for _ in range(n)]
        for i in range(n):
            for word in words:
                count[i][ord(word[i]) - ord('a')] += 1
        
        for i in range(n):
            for j in range(m - 1, -1, -1):
                dp[j + 1] += dp[j] * count[i][ord(target[j]) - ord('a')]
                dp[j + 1] %= mod
        
        return dp[m]