# Number of Ways to Form a Target String Given a Dictionary

This page explains Java solution to problem `Number of Ways to Form a Target String Given a Dictionary` using `Dynamic Programming` algorithm.

## Problem Statement

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) of target, you can choose the `kth` character of the `jth` string in words if `target[i] = words[j][k]`.
• Once you use the `kth` character of the `jth` string of words, you can no longer use the xth character of any string in words where `x `
• 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")

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

public int numWays(String[] words, String target) {
long MOD = (int)1e9 + 7;
int n = target.length();
long[] dp = new long[n + 1];
dp = 1;
for(int wIndex = 0; wIndex < words.length(); wIndex++) {
int[] count = new int;
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];
}
}
``````

## Time Complexity

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

## Space Complexity

O(T) Where
T is length of input target string