FastPrep
Problem · Dynamic Programming

String Formation

Learn this problem
● HardAtlassian logoAtlassianINTERNFULLTIMEOA

Problem statement

All words have equal length. Form target by choosing its characters from strictly increasing column indices; at a chosen column, the character may come from any word. Count distinct index-and-word choices modulo 10^9 + 7.

Function

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

Examples

Example 1

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

There are two choices for 'a' in column zero and two choices for 'c' in column two.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 3000
  • 1 <= target.length <= words[i].length
  • All characters are lowercase English letters.

More Atlassian problems

drafts saved locally
public int numWays(String[] words, String target) {
  // Write your code here.
}
words["adc","aec","efg"]
target"ac"
expected4
checking account