g1601_1700.s1639_number_of_ways_to_form_a_target_string_given_a_dictionary.Solution

public class Solution extends Object

1639 - Number of Ways to Form a Target String Given a Dictionary.Hard You are given a list of strings of the same length <code>words</code> and a string <code>target</code>. Your task is to form <code>target</code> using the given <code>words</code> under the following rules: <ul> <li><code>target</code> should be formed from left to right.</li> <li>To form the <code>ith</code> character ( 0-indexed ) of <code>target</code>, you can choose the <code>kth</code> character of the <code>jth</code> string in <code>words</code> if <code>target[i] = words[j][k]</code>.</li> <li>Once you use the <code>kth</code> character of the <code>jth</code> string of <code>words</code>, you can no longer use the <code>xth</code> character of any string in <code>words</code> where <code>x <= 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> Notice that you can use multiple characters from the same string in <code>words</code> provided the conditions above are met. Return the number of ways to form <code>target</code> from <code>words</code>. Since the answer may be too large, return it modulo <code>109 + 7</code>. 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: <ul> <li><code>1 <= words.length <= 1000</code></li> <li><code>1 <= words[i].length <= 1000</code></li> <li>All strings in <code>words</code> have the same length.</li> <li><code>1 <= target.length <= 1000</code></li> <li><code>words[i]</code> and <code>target</code> contain only lowercase English letters.</li> </ul>

Constructor Summary

Constructors

Constructor

Description

Solution()
Method Summary

Modifier and Type

Method

Description

int

numWays(String[] words, String target)

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- Solution
  
  public Solution()
Method Details
- numWays
  
  public int numWays(String[] words, String target)

Class Solution

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

Solution

Method Details

numWays