Given an array of strings A, each of the same length and a target string S, find the number of ways to construct the target string using characters from strings in the given array such that the indices of the characters used in string construction form a strictly increasing sequence. Multiple characters can also be used from the same string. Since the answer can be very large, take modulo with (10^9 + 7)
Answers
Answer:
Given an array of strings A, each of the same length and a target string S, find the number of ways to construct the target string using characters from strings in the given array such that the indices of the characters used in string construction form a strictly increasing sequence. Multiple characters can also be used from the same string. Since the answer can be very large, take modulo with (10^9 + 7)
Examples:
Input : A = ["adc", "aec", "erg"], S = "ac"
Output : 4
Target string can be formed in following ways :
1) 1st character of "adc" and the 3rd character of "adc".
2) 1st character of "adc" and the 3rd character of "aec".
3) 1st character of "aec" and the 3rd character of "adc".
4) 1st character of "aec" and the 3rd character of "aec".
Input : A = ["afsdc", "aeeeedc", "ddegerg"], S = "ae"
Output : 12
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach
We will use Dynamic Programming to solve the problem.
For each string in the array, store the positions in which characters occurred in the string in a common list (L). Our aim is to use the characters whose indices form a strictly increasing sequence, so it doesn’t matter which string they come from.
Traverse the target string, and keep the information of previously picked index (prev). For the current position of the target string check whether this character has occurred at any index greater than prev by searching in L. This can be done naively using recursion but we can memoize it using dp table.