給出一堆候選單詞words和目標(biāo)字符串target，依次從候選單詞的某一個(gè)選擇字符拼成target，如果某個(gè)單詞的第x位被選過(guò)了，則之后無(wú)法再選擇任意單詞<=x位置的任何字符，問(wèn)一共多少種選取方法，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