Meesho Coding Question – Solved

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 such that the indices of the characters in the order in which they are used form a strictly increasing sequence. Here the index of a character is the position at which it appears in the string. Note that it is acceptable to use multiple characters from the same string. Determine the number of ways to construct the target string. One construction is different from another if either the sequences of indices they use are different or the sequences are the same but there exists a character at some index such that it is chosen from a different string in these constructions. Since the answer can be very large, return the value modulo (10^9 + 7). Consider an example with n = 3 strings, each of length 3. Let the array of strings be words = ["adc", "aec", "efg"], and the target string target = "ac". There are 4 ways to reach the target: 1. Select the 15t 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 15t character of "aec" and the 3rd character of "adc". 4. Select the 1st character of "aec" and the 3rd character of "aec".