In my personal opinion, this stupid problem is harder than an ordinary DP, because:

state transition is weird(multiplication…)
we need another data structure to pre-compute something

Idea

We need to match chars in word and chars in target, but with the given restriction.

once we take a char in word, the char and the char to the left from all words are not available anymore
we can start from any word, not necessarily from the first word
target can be shorter than words[0]

Base Case

Success case: chars in targets are all matched(m>=len(target)). We return 1 as this is one solution.

Fail case: (1)words are used up and (2)some chars left unmatched in target. i>=len(words[0]), we reply on the success case check to handle (2).

DP States

word pointer(i)

Since we need to know what chars are available, we need to know what we have taken, so the index of word that we have already taken has to be one of the states.

target pointer(m)

This is straight forward, we need to know until which index, we have matched the chars.

Why we don’t need a pointer to record which word in words list we have used?

This is because we can start from any word.

State Transition

This is the hard part.

Let’s say we have dp(i,m)

We need to know how many word[i] is equal to target[m] so that we can match this pair of chars.

Assume there are x matches, then we have 2 options:

x==0
1. in this case, we have NO match, thus we have to proceed to i+1 without doing anything
2. so the transition is result=dp(i+1,m)
x>0
1. we have x matches and all these matches can combine with the next available matches(dp(i+1,m+1)), so we need to multiply them to get in how many ways we can match them.
2. so the transition is result=x*dp(i+1,m+1)

Algorithm

We have DP states, transitions, usually we can code the solution at this point but we have one more thing to settle, how do we calculate x(how many word[i] is equal to target[m] so that we can match this pair of chars)?

We need to do a pre-processing, to calculate the lower case english letters count at each i

1
2
3
4
5


swlen=len(words[0])
charcount=[[0 for _ in range(26)] for _ in range(swlen)]
    for i in range(swlen):
        for word in words:
            charcount[i][ord(word[i])-97]+=1

Now we’re ready to go!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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

        charcount=[[0 for _ in range(26)] for _ in range(swlen)]
        for i in range(swlen):
            for word in words:
                charcount[i][ord(word[i])-97]+=1
        @functools.cache
        def dp(i,m):
            if m>=tlen:
                return 1
            if i>=swlen:
                return 0
            res=0
            match_char_count=charcount[i][ord(target[m])-97]
            if match_char_count>0:
                res+=match_char_count*dp(i+1,m+1)
            res+=dp(i+1,m)
            return res%MOD
        return dp(0,0)

Idea#

Base Case#

DP States#

word pointer(i)#

target pointer(m)#

State Transition#

Algorithm#