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.- To form the
ith
character (0-indexed) oftarget
, you can choose thekth
character of thejth
string inwords
iftarget[i] = words[j][k]
. - Once you use the
kth
character of thejth
string ofwords
, you can no longer use thexth
character of any string inwords
wherex <= k
. In other words, all characters to the left of or at indexk
become unusuable for every string. - Repeat the process until you form the 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")
Example 3:
Input: words = ["abcd"], target = "abcd" Output: 1
Example 4:
Input: words = ["abab","baba","abba","baab"], target = "abba" Output: 16
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 1000
- All strings in
words
have the same length. 1 <= target.length <= 1000
words[i]
andtarget
contain only lowercase English letters.
Solution: DP
dp[i][j] := # of ways to form target[0~j] where the j-th letter is from the i-th column of words.
count[i][j] := # of words that have word[i] == target[j]
dp[i][j] = dp[i-1][j-1] * count[i][j]
Time complexity: O(mn)
Space complexity: O(mn) -> O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int numWays(vector<string>& words, string target) { constexpr int kMod = 1e9 + 7; const int n = target.length(); const int m = words[0].length(); vector<long> dp(n); // dp[j] = # of ways to form t[0~j] for (int i = 0; i < m; ++i) { vector<int> count(26); for (const string& word: words) ++count[word[i] - 'a']; for (int j = min(i, n - 1); j >= 0; --j) dp[j] = (dp[j] + (j > 0 ? dp[j - 1] : 1) * count[target[j] - 'a']) % kMod; } return dp[n - 1]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment