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:
targetshould be formed from left to right.- To form the
i^thcharacter (0-indexed) oftarget, you can choose thek^thcharacter of thej^thstring inwordsiftarget[i] = words[j][k]. - Once you use the
k^thcharacter of thej^thstring ofwords, you can no longer use thex^thcharacter of any string inwordswherex <= k. In other words, all characters to the left of or at indexkbecome unusable 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
6There are 6 ways to form target using increasing column indices from the given words.
Example 2
Input
words = ["abba","baab"], target = "bab"Output
4There are 4 ways to form target using increasing column indices from the given words.
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.