Number Of Ways To Form A Target String Given A Dictionary
01 · Problem
You are given a list of strings words, all of the same length m, and a string target. Think of words as a grid with m columns. Build target from left to right as follows:
- To form
target[i], choose some word and some columncsuch that that word has the lettertarget[i]at columnc. - The column chosen for
target[i + 1]must be strictly greater than the column chosen fortarget[i]. Once a column is used, every column at or left of it becomes unusable for all words. - Different target characters may come from the same word or from different words.
Two ways are different if, for some i, they pick a different (word, column) for target[i]. Return the number of ways to form target. Because the answer can be huge, return it modulo 10^9 + 7. If target cannot be formed, return 0.
02 · Examples
words = ["abba","baab"], target = "ab"
6
Every column holds exactly one 'a' and one 'b'. Pick any two columns i < j, take 'a' from column i and 'b' from column j: there are 6 column pairs with 1 * 1 choices each, so 6 ways.
words = ["aa","aa"], target = "aa"
4
Column 0 offers 2 choices of 'a' and column 1 offers 2 choices, so there are 2 * 2 = 4 ways.
words = ["xyz"], target = "zx"
0
The 'z' is only in column 2, and nothing to its right can supply 'x', so there are 0 ways.
03 · Constraints
- 011 <= words.length <= 1000
- 021 <= words[i].length <= 1000, and all words have the same length
- 031 <= target.length <= 1000
- 04words[i] and target consist only of lowercase English letters
04 · Optimal complexity
- Time
- O(w * m + m * t)
- Space
- O(26 * m + t)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.