https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
不容易想到的问题转化和dp的推导

个人解答

  1. class Solution:
  2.     def numWays(self, words: List[str], target: str) -> int:
  3.         self.N = len(words[0])
  4.         self.frequency = {}
  5.         for ch in string.ascii_lowercase:
  6.             self.frequency[ch] = [0] * self.N
  7.         # record char frequency
  8.         for w in words:
  9.             for i, ch in enumerate(w):
  10.                 self.frequency[ch][i] += 1
  12.         @functools.lru_cache(None)
  13.         def f(targetIdx, wordsIdx):
  14.             if targetIdx == len(target):
  15.                 return 1
  16.             if wordsIdx == self.N:
  17.                 return 0
  19.             res = 0
  20.             # not choose char at current wordsIdx
  21.             res += f(targetIdx, wordsIdx + 1)
  22.             # choose current char
  23.             ch = target[targetIdx]
  24.             if self.frequency[ch][wordsIdx] > 0:
  25.                 res += self.frequency[ch][wordsIdx] * f(targetIdx + 1, wordsIdx + 1)
  26.             return res
  28.         return f(0, 0) % (10**9 + 7)

题目分析

参考：https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/discuss/917694/JavaPython-Top-Down-DP-Clean-and-Concise-O(m*n))

题目主要分为两步，单独每一步看都不算太难，但是整个题目不容易想到这两步。

1. 构建对应idx的频率表

其实题目条件给出的，所有word长度相同，便有这样的暗示，即，在只统计数量的情况下，选相同idx下不同word中的相同字母，是完全等效且与前后相互独立的！
因此，可以通过这一性质，简化输入，只保留在固定长度的word中，每个位置对应的各字母出现的频率，把一个二维问题，转化为了一维问题。

2. DP 0-1背包思想

0-1背包的思想可以用在很多的DP题目中，这道题便是很典型的应用，统计数量时，分两种情况讨论：

  • 选择当前位置的字符
  • 不选择当前位置的字符

如此经典的思想，几乎在一维DP中都会用到

除此之外，处理下特殊情况，就可以了

其它解法

题解里给出的是Top-Down的解法，得益于python的 lru_cache ，写起来比较直观，也不用显式memorize，当然也可以采用bottom-up的方式。