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:
target should be formed from left to right.ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.target.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 109 + 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 <= 10001 <= words[i].length <= 1000words have the same length.1 <= target.length <= 1000words[i] and target contain only lowercase English letters.This approach utilizes dynamic programming along with a frequency table to keep track of the count of each character at each column index across the given words. We calculate ways to form the target string by building up solutions to subproblems of forming prefixes of the target string using the letter frequency information efficiently.
This solution constructs a DP table where `dp[i][j]` represents the number of ways to form the first `i` characters of the target using the first `j` characters (positions) of the words. The `count` table stores how many times each character appears at each position in `words`. We update the DP table row by row for each position in the target by combining counts from the `count` table and previous DP states.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m + m*t), where n is the number of words, m is the length of each word, and t is the length of the target string.
Space Complexity: O(m*t).
This approach uses memoization to optimize the recursion while forming the target. We compute ways from each index of target and position of words and save computed results to avoid redundant calculations. This approach is effective in reducing the exponential time complexity without deep overlapping subproblems.
This solution employs a recursive depth-first search (`dfs`) with memoization. The function `dfs(i, j)` returns the number of ways to form the target string starting from index `i` of the target and index `j` of a word in `words`. The memoized `dp` array stores results of overlapping subproblems to avoid recalculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).
| Approach | Complexity |
|---|---|
| Dynamic Programming with Character Frequency Table | Time Complexity: O(n*m + m*t), where n is the number of words, m is the length of each word, and t is the length of the target string. |
| Memoization Approach | Time Complexity: O(n*m + m*t), optimized with memoization. |
Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - Python • NeetCodeIO • 11,938 views views
Watch 9 more video solutions →Practice Number of Ways to Form a Target String Given a Dictionary with our built-in code editor and test cases.
Practice on FleetCode