1639.Number of Ways to Form a Target String Given a Dictionary
===

###### tags: `Hard`,`Array`,`String`,`DP`

[1639. Number of Ways to Form a Target String Given a Dictionary](https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/)

### 題目描述

You are given a list of strings of the **same length** `words` and a string `target`.

Your task is to form `target` using the given `words` under the following rules:

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

**Notice** that you can use **multiple characters** from the **same string** in `words` provided the conditions above are met.

Return *the number of ways to form* `target` *from* `words`. Since the answer may be too large, return it **modulo** 10^9^ + 7.

### 範例

**Example 1:**

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

**Example 2:**

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

**Constraints**:

* 1 <= `words.length` <= 1000
* 1 <= `words[i].length` <= 1000
* All strings in `words` have the same length.
* 1 <= `target.length` <= 1000
* `words[i]` and `target` contain only lowercase English letters.

### 解答

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)