https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary

Let us denote by dp[i][j] number of solutions, such that the last symbol we take was from i-th column and also we create exactly j symbold of our target. Let also sp[i][j] be cumulative sum of dp on first index, that is sp[i][j] = sp[i-1][j] + ... + sp[0][j].

Now, the question is how we an evaluate dp[i][j]. By definition, the last symbol we take is from i-th column. So, first, we need to understand how many options we have to take this symbol: for quick acces we use Q[i][j] array, how many times we have symbol j in i-th column. We need to multiply this number by sp[i-1][j-1] = dp[0][j-1] + ... + dp[i-1][j-1], because previous taken symbol can be from any of previous columns. For example, it can happen, that Q[i][ord(target[j]) - ord("a")] = 0, it means that dp[i][j] = 0 immedietly. Also we need to consider one more corner case: if j = 0, it means, we just start to build our target string, so in this case we do not need to multiply by sp[i-1][j-1]. Finally, we update our sp and do not forget to use modulo N.

Complexity: space complexity is O(26n + nk) to keep our Q, dp and sp tables. Time complexity is O(nm + nk) to form Q table and to update dp and sp tables.

class Solution:
    def numWays(self, words, target):
        m, n, k, N = len(words), len(words[0]), len(target), 10**9 + 7
        Q  = [[0] * 26 for _ in range(n)]
        dp = [[0] * k for _ in range(n)]
        sp = [[0] * k for _ in range(n)]
        for i in range(n):
            for j in range(m):
                Q[i][ord(words[j][i]) - ord("a")] += 1

        dp[0][0] = sp[0][0] = Q[0][ord(target[0]) - ord("a")]
        
        for i in range(1, n):
            for j in range(k):
                if j > 0: dp[i][j] = Q[i][ord(target[j]) - ord("a")] * sp[i-1][j-1]
                else: dp[i][j] = Q[i][ord(target[j]) - ord("a")]
                sp[i][j] = (sp[i-1][j] + dp[i][j]) % N

        return sp[-1][-1] % N

If you like the solution, you can upvote it on leetcode discussion section: Problem 1639