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:
targetshould be formed from left to right.- To form the
ithcharacter (0-indexed) oftarget, you can choose thekthcharacter of thejthstring inwordsiftarget[i] = words[j][k]. - Once you use the
kthcharacter of thejthstring ofwords, you can no longer use thexthcharacter of any string inwordswherex <= k. In other words, all characters to the left of or at indexkbecome 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 <= 10001 <= words[i].length <= 1000- All strings in
wordshave the same length. 1 <= target.length <= 1000words[i]andtargetcontain 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.
huahualeetcode
Be First to Comment