给出一堆候选单词words和目标字符串target，依次从候选单词的某一个选择字符拼成target，如果某个单词的第x位被选过了，则之后无法再选择任意单词<=x位置的任何字符，问一共多少种选取方法，DP
思路参考->https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/solutions/3421395
1 #1639
2 #Runtime: 1314 ms (Beats 75%)
3 #Memory: 27.5 MB (Beats 100%)
4
5 class Solution(object):
6 def numWays(self, words, target):
7 """
8 :type words: List[str]
9 :type target: str
10 :rtype: int
11 """
12 l = len(words[0])
13 n = len(target)
14 dp = [0] * (n + 1)
15 dp[0] = 1
16 cnt = [[0] * 26 for _ in range(l)]
17 for i in range(l):
18 for word in words:
19 cnt[i][ord(word[i]) - ord('a')] += 1
20 for i in range(l):
21 for j in range(n - 1, -1, -1):
22 dp[j + 1] = (dp[j + 1] + dp[j] * cnt[i][ord(target[j]) - ord('a')]) % (10**9 + 7)
23 return dp[n]
24