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.class Solution {
public:
int numWays(vector<string>& words, string target) {
int n = target.length(), mod = 1e9 + 7;
vector<long> res(n + 1);
res[0] = 1;
for (int i = 0; i < words[0].length(); ++i) {
vector<int> count(26);
for (auto& w : words)
count[w[i] - 'a']++;
for (int j = n - 1; j >= 0; --j) {
res[j + 1] += res[j] * count[target[j] - 'a'] % mod;
}
}
return res[n] % mod;
}
};class Solution {
public int numWays(String[] words, String target) {
int wordLength = words[0].length();
int targetLength = target.length();
final int MOD = 1_000_000_007;
//Step 1: Calculate frequency of each character at every index in "words".
int[][] charFrequency = new int[wordLength][26];
for (String word : words) {
for (int j = 0; j < wordLength; j++) {
charFrequency[j][word.charAt(j) - 'a']++;
}
}
//Step 2: Initialize two DP arrays: prev and curr.
long[] prevCount = new long[targetLength + 1];
long[] currCount = new long[targetLength + 1];
//Base case: There is one way to form an empty target string.
prevCount[0] = 1;
//Step 3: Fill the DP arrays.
for (int currWord = 1; currWord <= wordLength; currWord++) {
// Copy the previous row into the current row for DP.
System.arraycopy(prevCount, 0, currCount, 0, currCount.length);
for (int currTarget = 1; currTarget <= targetLength; currTarget++) {
// If characters match, add the number of ways.
int curPos = target.charAt(currTarget - 1) - 'a';
currCount[currTarget] +=
(1L *
charFrequency[currWord - 1][curPos] *
prevCount[currTarget - 1]) %
MOD;
currCount[currTarget] %= MOD;
}
// Move current row to previous row for the next iteration.
System.arraycopy(currCount, 0, prevCount, 0, prevCount.length);
}
//Step 4: The result is in prev[targetLength].
return (int) prevCount[targetLength];
}
}