Number of Ways to Form a Target String Given a Dictionary
Hard · Dynamic Programming · about 35 minutes
Asked at Google, Amazon, Microsoft.
All strings in words have the same length. Build target left to right: to place target[i], pick a column k and any word whose k-th character equals it; afterwards no column ≤ k may be used again. Return the number of ways modulo 10⁹ + 7.