A DP problem solved by using a Knapsack problem way

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

This is this week’s biweekly contest problem. The solution is pretty similar to the Knapsack problem.

Explanation

words = ["acca","bbbb","caca"], target = "aba"

we firstly can get the following information

for the character ‘a’, for the location of different indexes, it has the following number of words:

for a:

index 0: [‘acca’]

index 1: [‘caca’]

index 2: []

index 3: [‘acca’, ‘caca’]

for b:

index 0: [‘bbbb’]

index 1: [‘bbbb’]

index 2: [‘bbbb’]

index 3: [‘bbbb’]

For the above example, we can have a DP table as below

    0     1      2       3 
a.  1     1      0       2  
b.  0     1*1.   1*(1+1) 1*(1+1+0)
a   0     0.     0*(...) 2*(0+1+2)

We can use a natively 2D DP without optimization.

A naively 2D DP without optimization

It has the time complexity of O(mn*m) as we don’t have the optimization.

It got TLE.

85 / 89 test cases passed.

# time complexity O(mnm), space O(mn)
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        s = set(target)
        d = collections.defaultdict(lambda : collections.defaultdict(int))
        for word in words:
            for i, char in enumerate(word):
                if char in s:d[char][i] += 1
        n = len(target)
        m = len(words[0])
        
        dp = [[0]*m for _ in range(n)]
        dp[0] = [d[target[0]][j] for j in range(m)]
        for i in range(1, n):
            for j in range(i, m):
                dp[i][j] = d[target[i]][j]*sum(dp[i-1][k] for k in range(j))
        return sum(dp[-1])%(10**9 + 7)

A naively 2D DP with time complexity optimization

We can use a prefix sum to optimize the time complexity as O(mn)

# time complexity O(mn), space O(mn)
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        s = set(target)
        d = collections.defaultdict(lambda : collections.defaultdict(int))
        for word in words:
            for i, char in enumerate(word):
                if char in s:d[char][i] += 1
        n = len(target)
        m = len(words[0])
        
        dp = [[0]*m for _ in range(n)]
        dp[0] = [d[target[0]][j] for j in range(m)]
        for k in range(1, m):
            dp[0][k] += dp[0][k-1]
        for i in range(1, n):
            for j in range(i, m):
                dp[i][j] = d[target[i]][j]*dp[i-1][j-1]
            for k in range(i + 1, m):
                dp[i][k] += dp[i][k-1]
        return dp[-1][-1]%(10**9 + 7)

Bottom UP DP with time/space complexity optimization

# time complexity O(mn), space O(m)
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        s = set(target)
        d = collections.defaultdict(lambda : collections.defaultdict(int))
        for word in words:
            for i, char in enumerate(word):
                if char in s:d[char][i] += 1
        n = len(target)
        m = len(words[0])
        
        dp = [1]*m
        for i in range(n):
            new_dp = [0]*m
            for j in range(i, m):
                new_dp[j] = dp[j-1]*d[target[i]][j]
            for k in range(i, m):
                if k > 0: new_dp[k] += new_dp[k-1]
            dp = new_dp
        return dp[-1]%(10**9 + 7)

Thanks for reading.