<p>You are given a list of strings of the <strong>same length</strong> <code>words</code> and a string <code>target</code>.</p>

<p>Your task is to form <code>target</code> using the given <code>words</code> under the following rules:</p>

<ul>
	<li><code>target</code> should be formed from left to right.</li>
	<li>To form the <code>i<sup>th</sup></code> character (<strong>0-indexed</strong>) of <code>target</code>, you can choose the <code>k<sup>th</sup></code> character of the <code>j<sup>th</sup></code> string in <code>words</code> if <code>target[i] = words[j][k]</code>.</li>
	<li>Once you use the <code>k<sup>th</sup></code> character of the <code>j<sup>th</sup></code> string of <code>words</code>, you <strong>can no longer</strong> use the <code>x<sup>th</sup></code> character of any string in <code>words</code> where <code>x &lt;= k</code>. In other words, all characters to the left of or at index <code>k</code> become unusuable for every string.</li>
	<li>Repeat the process until you form the string <code>target</code>.</li>
</ul>

<p><strong>Notice</strong> that you can use <strong>multiple characters</strong> from the <strong>same string</strong> in <code>words</code> provided the conditions above are met.</p>

<p>Return <em>the number of ways to form <code>target</code> from <code>words</code></em>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;acca&quot;,&quot;bbbb&quot;,&quot;caca&quot;], target = &quot;aba&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 6 ways to form target.
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 1 (&quot;b<u>b</u>bb&quot;), index 3 (&quot;cac<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;cac<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 1 (&quot;b<u>b</u>bb&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 1 (&quot;c<u>a</u>ca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 1 (&quot;c<u>a</u>ca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;cac<u>a</u>&quot;)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abba&quot;,&quot;baab&quot;], target = &quot;bab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 ways to form target.
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 1 (&quot;b<u>a</u>ab&quot;), index 2 (&quot;ab<u>b</u>a&quot;)
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 1 (&quot;b<u>a</u>ab&quot;), index 3 (&quot;baa<u>b</u>&quot;)
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 2 (&quot;ba<u>a</u>b&quot;), index 3 (&quot;baa<u>b</u>&quot;)
&quot;bab&quot; -&gt; index 1 (&quot;a<u>b</u>ba&quot;), index 2 (&quot;ba<u>a</u>b&quot;), index 3 (&quot;baa<u>b</u>&quot;)
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 1000</code></li>
	<li>All strings in <code>words</code> have the same length.</li>
	<li><code>1 &lt;= target.length &lt;= 1000</code></li>
	<li><code>words[i]</code> and <code>target</code> contain only lowercase English letters.</li>
</ul>

class Solution:
    # what are the range of values len(words) can take on? [1, 1000]
    # what are the range of values len(words[i]) can take on? [1, 1000]
    #    ^^^ all words in words array have same length
    # what are the range of values len(target) can take on? [1, 1000]
    # what are the range of values target[i] can take on? english lower case letters ; same with words[i]
    # can words array be a null reference? no
    # can words[i] be a null reference? no
    # can target be a null reference? no
    # can we mutate the words array? no
    # we are returning an integer!
    # is the words array sorted in any particular order? no
    # are the words in words array unique? no?
    # is the answer unique? yes
    # is the answer >= 0? yes
    # can target be a word in the words array? maybe

    # idea 0
    # brute force dfs + backtracking
    
    # idea 1
    # same as idea 0 but use a cache with your dfs() helper method
    # use a cache to output the number of ways possible with the kth index
    #  ^^^ our cache should take two dimensions; same with dfs()
    # k = letter idx
    # i = word idx
    # example 1
    # verbal explanation given
    # pseudocode
    # N,n = len(words),len(words[0])
    # define hashmap cache dp
    # def dfs(i,k,currWord):
    #    if i == len(word):
    #       return 0
    #    if k == len(word[i]):
    #       return 0
    #    if len(currWord) > target:
    #       return 0
    #    if (i,k) in dp:
    #       return dp[(i,k)]
    #    if ''.join(currWord) == target:
    #        dp[(i,k)] = 1
    #        return 1
    #    res = 0
    #    for wordIdx in range(i,N):
    #      for letterIdx in range(k,n):
    #         if words[wordIdx][letterIdx] == target[len(currWord)]:
    #            currWord.append(words[wordIdx][letterIdx])
    #            res += dfs(wordIdx,letterIdx+1,currWord)
    #            currWord.pop()
    #    dp[(i,k)] = res
    #    return res
    # dfs(0,0)
    # return dp(0,0,[]) % (10**9 + 7)

    def numWays(self, words: List[str], target: str) -> int:
        # implement idea 1 (dfs + backtracking + memoization) <<< doesn't work
        # N,n = len(words),len(words[0])
        # dp = {}
        # def dfs(i,k,currWord):
        #     if (i == len(words) or
        #         len(currWord) > len(target)):
        #         # (i,k) in dp):
        #         return 0
        #     if ''.join(currWord) == target:
        #         # dp[(i,k)] = 1
        #         return 1
        #     res = 0
        #     for wordIdx in range(i,N):
        #         for letterIdx in range(k,n):
        #             if words[wordIdx][letterIdx] == target[len(currWord)]:
        #                 currWord.append(words[wordIdx][letterIdx])
        #                 res += dfs(wordIdx,letterIdx+1,currWord)
        #                 currWord.pop()
        #     # dp[(i,k)] = res
        #     return res
        # return dfs(0,0,[]) % (10**9 + 7)
        # # return dp[(0,0)] % (10**9 + 7)

        # LeetCode Editorial Approach 1 (Bottom Up DP)
        n=len(words[0])
        freqMap = [[0 for _ in range(n)] for _ in range(26)]
        # ^^^ NOTE: tells you how many of each letter (first dimension) exists
        #     at the i-th index (second dimension) among ALL words in the 'words' array
        for letterIdx in range(n):
            for word in words:
                freqMap[ord(word[letterIdx])-ord('a')][letterIdx] += 1
        dp = [[0 for _ in range(n+1)] for _ in range(len(target)+1)]
        # ^^^ NOTE: dp[i][j] = number of ways to form target[:i] with just the first j characters of ALL words in the 'words' array
        dp[0][0]=1 # <<< can only form empty string with no letters at all in 1 way
        for length in range(len(target)+1):
            for letterIdx in range(n):
                # NOTE: 'length' and 'letterIdx' are 0-based indices, yet
                #    dp's dimensions are 1-based. Therefore, we must eventually
                #    add 1 to both 'length' and 'letterIdx' when setting dp[...][...]
                if length < len(target): # <<< must avoid off-by-one error b/c we'll soon add 1 to 'length'
                    dp[length+1][letterIdx+1] += (
                        # NOTE: the indices of freqMap are NOT 1-based, but 0-based
                        freqMap[ord(target[length])-ord('a')][letterIdx] * dp[length][letterIdx]
                        # ^^^ what we are doing here is finding all occurrences of target[length] available at word[i][letterIdx] for all i in [0,1,..,n-1]
                        #    and then multiplying that frequency by the number of ways
                        #    already found by inspecting word[i][:lengthIdx] for all i in [0,1,...,n-1]
                        #    in order to build target[:length]
                    )
                dp[length][letterIdx+1] += dp[length][letterIdx]
        return dp[len(target)][n] % ((10**9)+7)
1802