This page explains Java solution to problem Number of Ways to Form a Target String Given a Dictionary
using Dynamic Programming
algorithm.
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
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 2: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")
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")
package com.vc.hard;
class NumberOfWaysToFormATargetStringGivenADictionary {
public int numWays(String[] words, String target) {
long MOD = (int)1e9 + 7;
int n = target.length();
long[] dp = new long[n + 1];
dp[0] = 1;
for(int wIndex = 0; wIndex < words[0].length(); wIndex++) {
int[] count = new int[26];
for(String word: words) {
count[word.charAt(wIndex) - 'a']++;
}
for(int targetIndex = n - 1; targetIndex >= 0; targetIndex--) {
dp[targetIndex + 1] += dp[targetIndex] * count[target.charAt(targetIndex) - 'a'];
if(dp[targetIndex + 1] < 0) dp[targetIndex + 1] += MOD;
else dp[targetIndex + 1] %= MOD;
}
}
return (int)dp[n];
}
}
O(L * (W + T)) Where
L is length of input words array
W is length of any input word in an input words array
T is length of input target string
O(T) Where
T is length of input target string