FastPrep
Problem · Dynamic Programming

String Formation (Also for AI/ML Software Engineer Intern :)

Learn this problem
● HardSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

Given an array of strings, each with the same length, and a target string, create the target string using characters from the strings in the given array such that the indices of the characters form a strictly increasing sequence. The index of a character is its position within the string, and multiple characters from the same string can be used.

Determine the number of ways to form the target string. Each construction is different if the sequences of indices used are different or if the sequences are the same but the characters are chosen from different strings at any index. Since the answer can be very large, return the result modulo 10^9 + 7.

Function

numWays(words: String[], target: String) → int

Complete the function numWays in the editor with the following parameters:

  • string words[n]: an array of strings
  • string target: the target string

Returns

int: the number of ways, modulo 10^9 + 7

Examples

Example 1

words = ["valya", "lyglb", "vldoh"]target = "val"return = 4

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

words = ["adc", "aec", "efg"]target = "ac"return = 4

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.

More Snowflake problems

drafts saved locally
public int numWays(String[] words, String target) {
  // write your code here
}
words["valya", "lyglb", "vldoh"]
target"val"
expected4
checking account