Last Updated: 17 Sep, 2021
Ninja and Strings
Moderate
Asked in company
Ninja found an old book having ‘N’ strings of equal length. By reading all these strings, Ninja thought of a ‘TARGET’ string in his mind and wanted to form this target string using these ‘N’ strings. The formation of the string should follow the following conditions:
1. The indices of characters in the order in which they are used should form a strictly increasing order.
2. You can use multiple characters from one string.
Your task is to find the total number of ways in which the ‘TARGET’ string can be formed. Two ways are said to be different if the sequence of indices is different or the sequence is the same but chosen from different strings. The number of ways can be very large so return its mod 10^9 + 7.
For Example
For the given ‘WORDS’ = [ "acca","bbbb","caca" ], and ‘TARGET’ = "aba".
There are 6 ways to form the ‘TARGET’ string.
"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")
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N’, denoting the number of strings in the ‘WORDS’ array.
The second line contains ‘N’ strings denoting the ‘N’ strings found in the book.
The third line contains the ‘TARGET’ string.
Output Format:
For each test case, print an integer corresponding to the number of ways to form the ‘TARGET’ string % (10^9 +7).
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000.
1 <= length of strings in ‘WORDS’ array<=1000.
1 <= length of ‘TARGET’ string <= length of WORDS[i] .
Time limit: 1 sec
Approaches
In this approach, we will declare a recursive function HELPER(‘CUR’, ‘IDX’,’ FREQ’,’TARGET’) that will return the number of the ways to create the substring of ‘TARGET[0..CUR]’. ‘IDX’ represents the current position in ‘WORDS’ array. ’FREQ’ is a 2-D matrix as ‘FREQ[i][c]’ represents the count of character ‘c’ at index ‘i’ in strings of ‘WORDS’ array.
The base case will be if CUR is equal to the length of ‘TARGET’, return 1.
And if ‘IDX’ is equal to the length of the string in the ‘WORDS’ array, we don’t have any characters left, so return 0.
The answer for this sub-problem will be HELPER(‘CUR’,’IDX’+1,’FREQ’,’TARGET’) (Skipping the ‘IDX’ index of ‘WORDS’) + FREQ[ ‘IDX’ ][ ‘TARGET’[‘CUR’] - ‘a’]*HELPER(‘CUR’+1,’IDX’+1’, FREQ’,’ TARGET’)(Using the characters at ‘IDX’ index of ‘WORDS’).
We will first compute our ‘FREQ’ array to store the frequency of each character at specific indices of ‘WORDS’.At last, we will return HELPER(0,0,’FREQ’,’ TARGET’).
Algorithm:
- Defining function HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’).
- If ‘CUR’ is equal to the length of ‘TARGET’, return 1. (Base Case.)
- If ‘IDX’ is equal to the length of ‘TARGET’, return 0. (Base Case).
- Declare ‘ANS’ to store the answer to this sub-problem.
- Set ‘ANS’ as HELPER(‘CUR’, ’IDX’ + 1, ’FREQ’,’ TARGET’).
- Set ‘ANS’ as ( ANS + (HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’) * FREQ[ ‘IDX’ ][TARGET[CUR] - ‘a’]) % (10^9 + 7) ) % (10^9 + 7).
- Return ‘ANS’.
- Declare a 2-D matrix ‘FREQ’ of size[ length of WORDS[0] ][26] to store the frequency of character ‘C’ at ‘i’th index in ‘WORDS’ array as ‘FREQ’[i][‘C’].
- Initialize all values of ‘FREQ’ with 0.
- For each ‘WORD’ in ‘WORDS’, do the following:
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- Set FREQ[i][WORD[i]- ‘a’] = FREQ[i][WORD[i]- ‘a’] + 1.
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- Set ‘ANS’ as HELPER(0,0, ’FREQ’, ’TARGET’).
- Return ‘ANS’.
As in the approach-1, we have used a recursive function to find the answer. We will use the same function in this approach, but we will store the answer returned by the function in a DP array. So that if the answer is already computed, we can use that answer and reduce the time complexity efficiently.
Algorithm:
- Defining function HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’, ’DP’).
- If ‘CUR’ is equal to the length of ‘TARGET’, return 1. (Base Case.)
- If ‘IDX’ is equal to the length of ‘TARGET’, return 0. (Base Case).
- If DP[‘CUR’][‘IDX’] is not equal to -1, value is already computed:
- Return DP[‘CUR’][‘IDX’].
- Declare ‘ANS’ to store the answer to this sub-problem.
- Set ‘ANS’ as HELPER(‘CUR’, ’IDX’ + 1, ’FREQ’,’ TARGET’, ’DP’).
- Set ‘ANS’ as ( ANS + (HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’, ’DP’) * FREQ[ ‘IDX’ ][TARGET[CUR] - ‘a’]) % (10^9 + 7) ) % (10^9 + 7).
- Set DP[‘CUR’][‘IDX’] as ‘ANS’.
- Return ‘ANS’.
- Declare a 2-D matrix ‘FREQ’ of size[ length of WORDS[0] ][26] to store the frequency of character ‘C’ at ‘i’th index in ‘WORDS’ array as ‘FREQ’[i][‘C’].
- Initialize all values of ‘FREQ’ with 0.
- For each ‘WORD’ in ‘WORDS’, do the following:
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- Set FREQ[i][WORD[i]- ‘a’] = FREQ[i][WORD[i]- ‘a’] + 1.
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- Declare a ‘DP’ table to memoize this DP solution.
- Set all values of ‘DP’ as -1.
- Set ‘ANS’ as HELPER(0,0, ’FREQ’, ’TARGET’, ’DP’).
- Return ‘ANS’.
In this approach, we will declare a DP table of size (length of ‘TAREGT’ string + 1 * length of the string in ‘WORDS’ array + 1).DP[i][j] will denote the answer for ‘TARGET[0..i]’ and considering only the first j characters of each string in ‘WORDS’.
We will first compute ‘FREQ’ array.
’FREQ’ is a 2-D matrix as ‘FREQ[i][c]’ represents the count of character ‘c’ at index ‘i’th in strings of ‘WORDS’ array.
Now we will fill the ‘DP’ table in the following manner:
- If i == 0 , ‘DP’[i][j] is 1.
- If j==0,’DP’[i][j] is 0 as no character left.
- Otherwise ‘DP’[i][j] = ‘DP’[i][j-1] (Skipping the jth characters of ‘WORDS’ array) + ( ‘DP’[i-1][j-1] * ‘FREQ’[j-1][‘TARGET’[i-1] - ‘a’](Using the jth characters of ‘WORDS’ array).
So our final answer will be ‘DP’[length of ‘TAREGT’ string][ length of string in ‘WORDS’ array].
Algorithm:
- Declare ‘DP’ table of size (length of ‘TAREGT’ string + 1) * )length of the string in ‘WORDS’ array + 1).
- Declare a 2-D matrix ‘FREQ’ of size[ length of ‘WORDS’[0] ][26] to store the frequency of character ‘C’ at ‘i’th index in ‘WORDS’ array as ‘FREQ’[i][‘C’].
- Initialize all values of ‘FREQ’ with 0.
- For each ‘WORD’ in ‘WORDS’, do the following:
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- Set FREQ[i][WORD[i]- ‘a’] = ‘FREQ’[i][‘WORD’[i]- ‘a’] + 1.
- For each index ‘i’ in the range from 0 to length of ‘WORD’, do the following:
- For i in range 0 to the length of ‘TARGET’, do the following:
- For j in range 0 to length of ‘WORDS[0]’, do the following:
- If i is equal to 0,Set ‘DP’[i][j] as 1 and continue for next iteration.
- If j is equal to 0,Set ‘DP’[i][j] as 0 and continue for next iteration.
- Otherwise Set DP[i][j] as ( ‘DP’[i][j-1] + ( (‘FREQ’[ j-1 ][ ‘TARGET’[i-1]-’a’ ] * ‘DP’[i-1][j-1]) % (10^9 + 7) ) % (10^9 + 7).
- For j in range 0 to length of ‘WORDS[0]’, do the following:
- Return ‘DP’[length of ‘TAREGT’ string][ length of string in ‘WORDS’ array].
Similar problems