FastPrep

Description

Solutions

Submission

String Formation

🤘 INTERN

Given an array of strings, each of the same length, and a target string, construct the target string using characters from the strings in the given array in such a way that the indices of the characters used are in a strictly increasing sequence. Here, the index of a character is the position at which it appears in the string. Multiple characters can be used from the same string.

Determine the number of ways to construct the target string. Two constructions are considered different if either the sequences of indices they use are different or the sequences are the same but there exists a character at some index that is chosen from a different string. Return the value modulo (10^9 + 7).

Function Description

Complete the function numWays in the editor below.

numWays has the following parameters:

1. String words[n]: an array of strings
2. String target: the target string

Returns

int: an integer representing the number of ways, modulo (10⁹ + 7)

Example 1:

Input:  words = ["valya", "lyglb", "vldoh"], target = "val"
Output: 4 
Explanation:
There are 4 ways to construct the string "val" such that the indices will be in strictly increasing 
order.

1. Select the 1st character of "valya", the 2nd character of "valya" and the 3rd character of "valya".

2. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "lyglb".

3. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "vldoh".

4. Select the 1st character of "vldoh", the 2nd character of "valya" and the 3rd character of "valya".

Example 2:

Input:  words = ["adc", "aec", "efg"], target = "ac"
Output: 4 
Explanation:
There are 4 ways to reach the target:

1. Select the 1st character of "adc" and the 3rd character of "adc".
      
2. Select the 1st character of "adc" and the 3rd character of "aec".
      
3. Select the 1st character of "aec" and the 3rd character of "adc".
      
4. Select the 1st character of "aec" and the 3rd character of "aec".

Constraints:

1 ≤ n ≤ 10^3

1 ≤ length of words[i] ≤ 3000

All words[i] are of equal length per test case.

The sum of the lengths of all words[i] is ≤ 10^5.

1 ≤ length of target ≤ length of words[i]

All characters are lowercase English letters.