Number of Ways to Form a Target String Given a Dictionary
You are given a list of strings of the same length words and a string target.
You are given a list of strings of the same length words and a string target.
Your task is to form target using the given words under the following rules:
Notice that you can use multiple characters from the same string in words provided the conditions above are met.
Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.
Example 1
Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target. "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")
Example 2
Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target. "bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba") "bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab") "bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab") "bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 1000
- All strings in words have the same length.
- 1 <= target.length <= 1000
- words[i] and target contain only lowercase English letters.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.