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

 

A dynamic programming approach:

 

Let dp[i, j] be the total number of cases of target[i] corresponding to jth position

dp[i, j] = dp[i][j-1] + dp[i-1][j-1] * counter[j, target[i]]

 

1) Bottom-up

import string
from functools import lru_cache
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        
        N = len(words[0])
        freqs = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
        
        for word in words:
            for i, c in enumerate(word):
                freqs[i][c] += 1

        m = len(target)
        n = len(words[0])
        dp = [[0] * n for _ in range(m)]

        dp[0][0] = freqs[0][target[0]]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + freqs[i][target[0]]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j-1] * freqs[j][target[i]]
        return dp[-1][-1] % (10**9+7)

 

2) Top-down

import string
from functools import lru_cache
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        
        N = len(words[0])
        freqs = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
        
        for word in words:
            for i, c in enumerate(word):
                freqs[i][c] += 1

        m = len(target)
        n = len(words[0])
        dp = [[0] * n for _ in range(m)]

        @lru_cache(None)
        def dfs(i, j):
            nonlocal N, target
            if i == len(target):
                return 1
            if j == N:
                return 0

            return (freqs[j][target[i]] * dfs(i+1, j+1) + dfs(i, j+1)) % (10**9+7)

        return dfs(0, 0)