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

1. Recursion

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        mod = 10**9 + 7
        n, m = len(target), len(words[0])

        def dfs(i, k):
            if i == n:
                return 1
            if k == m:
                return 0

            res = dfs(i, k + 1)
            for w in words:
                if w[k] != target[i]:
                    continue
                res = (res + dfs(i + 1, k + 1)) % mod
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(N ^ m)$
Space complexity: $O(m)$

Where $N$ is the number of words, $m$ is the length of each word, and $n$ is the length of the $target$ string.

2. Dynamic Programming (Top-Down)

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        mod = 10**9 + 7
        cnt = defaultdict(int)  # (index, char) --> count among all words
        for w in words:
            for i, c in enumerate(w):
                cnt[(i, c)] += 1

        dp = {}

        def dfs(i, k):
            if i == len(target):
                return 1
            if k == len(words[0]):
                return 0
            if (i, k) in dp:
                return dp[(i, k)]

            c = target[i]
            dp[(i, k)] = dfs(i, k + 1)  # skip k position
            dp[(i, k)] += cnt[(k, c)] * dfs(i + 1, k + 1)
            dp[(i, k)] %= mod
            return dp[(i, k)]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * (n + N))$
Space complexity: $O(n * m)$

Where $N$ is the number of words, $m$ is the length of each word, and $n$ is the length of the $target$ string.

3. Dynamic Programming (Bottom-Up)

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

        cnt = [[0] * 26 for _ in range(m)]
        for word in words:
            for i, c in enumerate(word):
                cnt[i][ord(c) - ord('a')] += 1

        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[n][m] = 1

        for i in range(n, -1, -1):
            for k in range(m - 1, -1, -1):
                dp[i][k] = dp[i][k + 1]
                if i < n:
                    c = ord(target[i]) - ord('a')
                    dp[i][k] = (dp[i][k] + cnt[k][c] * dp[i + 1][k + 1]) % MOD

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * (n + N))$
Space complexity: $O(n * m)$

Where $N$ is the number of words, $m$ is the length of each word, and $n$ is the length of the $target$ string.

4. Dynamic Programming (Space Optimized)

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

        cnt = [[0] * 26 for _ in range(m)]
        for word in words:
            for i, c in enumerate(word):
                cnt[i][ord(c) - ord('a')] += 1

        dp = [0] * (m + 1)
        dp[m] = 1

        for i in range(n, -1, -1):
            nxt = 1 if i == n - 1 else 0
            for k in range(m - 1, -1, -1):
                cur = dp[k]
                dp[k] = dp[k + 1]
                if i < n:
                    c = ord(target[i]) - ord('a')
                    dp[k] = (dp[k] + cnt[k][c] * nxt) % MOD
                nxt = cur
            dp[m] = 0

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * (n + N))$
Space complexity: $O(m)$

Where $N$ is the number of words, $m$ is the length of each word, and $n$ is the length of the $target$ string.