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

1/**
2 * [1639] Number of Ways to Form a Target String Given a Dictionary
3 *
4 * You are given a list of strings of the same length words and a string target.
5 * Your task is to form target using the given words under the following rules:
6 * 
7 * 	target should be formed from left to right.
8 * 	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].
9 * 	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.
10 * 	Repeat the process until you form the string target.
11 * 
12 * Notice that you can use multiple characters from the same string in words provided the conditions above are met.
13 * Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.
14 *  
15 * Example 1:
16 * 
17 * Input: words = ["acca","bbbb","caca"], target = "aba"
18 * Output: 6
19 * Explanation: There are 6 ways to form target.
20 * "aba" -> index 0 ("<u>a</u>cca"), index 1 ("b<u>b</u>bb"), index 3 ("cac<u>a</u>")
21 * "aba" -> index 0 ("<u>a</u>cca"), index 2 ("bb<u>b</u>b"), index 3 ("cac<u>a</u>")
22 * "aba" -> index 0 ("<u>a</u>cca"), index 1 ("b<u>b</u>bb"), index 3 ("acc<u>a</u>")
23 * "aba" -> index 0 ("<u>a</u>cca"), index 2 ("bb<u>b</u>b"), index 3 ("acc<u>a</u>")
24 * "aba" -> index 1 ("c<u>a</u>ca"), index 2 ("bb<u>b</u>b"), index 3 ("acc<u>a</u>")
25 * "aba" -> index 1 ("c<u>a</u>ca"), index 2 ("bb<u>b</u>b"), index 3 ("cac<u>a</u>")
26 * 
27 * Example 2:
28 * 
29 * Input: words = ["abba","baab"], target = "bab"
30 * Output: 4
31 * Explanation: There are 4 ways to form target.
32 * "bab" -> index 0 ("<u>b</u>aab"), index 1 ("b<u>a</u>ab"), index 2 ("ab<u>b</u>a")
33 * "bab" -> index 0 ("<u>b</u>aab"), index 1 ("b<u>a</u>ab"), index 3 ("baa<u>b</u>")
34 * "bab" -> index 0 ("<u>b</u>aab"), index 2 ("ba<u>a</u>b"), index 3 ("baa<u>b</u>")
35 * "bab" -> index 1 ("a<u>b</u>ba"), index 2 ("ba<u>a</u>b"), index 3 ("baa<u>b</u>")
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= words.length <= 1000
41 * 	1 <= words[i].length <= 1000
42 * 	All strings in words have the same length.
43 * 	1 <= target.length <= 1000
44 * 	words[i] and target contain only lowercase English letters.
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
50// discuss: https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn num_ways(words: Vec<String>, target: String) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_1639() {
68    }
69}
70