# Explanation

`words = ["acca","bbbb","caca"], target = "aba"`
`    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)`

# A naively 2D DP without optimization

`# 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

`# 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)`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.