1639. Number of Ways to Form a Target String Given a Dictionary

[mah-shamim]

Topics: Array, String, Dynamic Programming

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 <= k. In other words, all characters to the left of or at index k 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")

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• All strings in words have the same length.
• 1 <= target.length <= 1000
• words[i] and target contain only lowercase English letters.

Hint:

1. For each index i, store the frequency of each character in the ith row.
2. Use dynamic programing to calculate the number of ways to get the target string using the frequency array.

[mah-shamim]

The problem requires finding the number of ways to form a target string from a dictionary of words, following specific rules about character usage. This is a combinatorial problem that can be solved efficiently using Dynamic Programming (DP) and preprocessing character frequencies.

Key Points

1. Constraints:
   • Words are of the same length.
   • Characters in words can only be used in a left-to-right manner.
2. Challenges:
   • Efficiently counting ways to form target due to large constraints.
   • Avoid recomputation with memoization.
3. Modulo:
   • Since the result can be large, all calculations are done modulo 109 + 7.

Approach

The solution uses:

1. Preprocessing:
   • Count the frequency of each character at every position across all words.
2. Dynamic Programming:
   • Use a 2D DP table to calculate the number of ways to form the target string.

Steps:

1. Preprocess words into a frequency array (counts).
2. Define a DP function to recursively find the number of ways to form target using the preprocessed counts.

Plan

1. Input Parsing:
   • Accept words and target.
2. Preprocess:
   • Create a counts array where counts[j][char] represents the frequency of char at position j in all words.
3. Dynamic Programming:
   • Use a recursive function with memoization to compute the number of ways to form target using characters from valid positions in words.
4. Return the Result:
   • Return the total count modulo 109 + 7.

Let's implement this solution in PHP: 1639. Number of Ways to Form a Target String Given a Dictionary

<?php
const MOD = 1000000007;
/**
 * @param String[] $words
 * @param String $target
 * @return Integer
 */
function numWays($words, $target) {
    $wordLength = strlen($words[0]);
    $targetLength = strlen($target);

    // Precompute character frequencies for each column
    $counts = array_fill(0, $wordLength, array_fill(0, 26, 0));
    foreach ($words as $word) {
        for ($j = 0; $j < $wordLength; $j++) {
            $counts[$j][ord($word[$j]) - ord('a')]++;
        }
    }

    // Memoization table
    $memo = array_fill(0, $targetLength, array_fill(0, $wordLength, -1));

    return dp(0, 0, $counts, $target, $memo);
}

/**
 * Helper function for DP
 *
 * @param $i
 * @param $j
 * @param $counts
 * @param $target
 * @param $memo
 * @return float|int|mixed
 */
private function dp($i, $j, $counts, $target, &$memo) {
    if ($i == strlen($target)) return 1; // Entire target formed
    if ($j == count($counts)) return 0; // Out of bounds
    if ($memo[$i][$j] != -1) return $memo[$i][$j];

    $ways = dp($i, $j + 1, $counts, $target, $memo); // Skip this column
    $charIndex = ord($target[$i]) - ord('a');

    if ($counts[$j][$charIndex] > 0) {
        $ways += dp($i + 1, $j + 1, $counts, $target, $memo) * $counts[$j][$charIndex];
        $ways %= Solution::MOD;
    }

    return $memo[$i][$j] = $ways;
}

// Example Usage
$words = ["acca", "bbbb", "caca"];
$target = "aba";
echo numWays($words, $target) . "\n"; // Output: 6

$words = ["abba", "baab"];
$target = "bab";
echo numWays($words, $target) . "\n"; // Output: 4
?>

Explanation:

1. Preprocessing Step:

   • Build a counts array:
     • For each column in words, count the occurrences of each character.
   • Example: If words = ["acca", "bbbb", "caca"], for the first column, counts[0] = {'a': 1, 'b': 1, 'c': 1}.

2. Recursive DP:

   • Define dp(i, j):
     • i is the current index in target.
     • j is the current position in words.
   • Base Cases:
     • If i == len(target): Entire target formed → return 1.
     • If j == len(words[0]): No more columns to use → return 0.
   • Recurrence:
     • Option 1: Use counts[j][target[i]] characters from position j.
     • Option 2: Skip position j.

3. Optimization:

   • Use a memoization table to store results of overlapping subproblems.

Example Walkthrough

Input:
words = ["acca", "bbbb", "caca"], target = "aba"

1. Preprocessing:

   • counts[0] = {'a': 2, 'b': 0, 'c': 1}
   • counts[1] = {'a': 0, 'b': 3, 'c': 0}
   • counts[2] = {'a': 1, 'b': 0, 'c': 2}
   • counts[3] = {'a': 2, 'b': 0, 'c': 1}

2. DP Calculation:

   • dp(0, 0): How many ways to form "aba" starting from column 0.
   • Recursively calculate, combining the use of counts and skipping columns.

Output: 6

Time Complexity

1. Preprocessing: O(n . m), where n is the number of words and m is their length.
2. Dynamic Programming: O(l . m), where l is the length of the target.
3. Total: O(n . m + l . m).

Output for Example

• Input:
  words = ["acca", "bbbb", "caca"], target = "aba"
• Output: 6

This problem is a great example of combining preprocessing and dynamic programming to solve a combinatorial challenge efficiently.

[basharul-siddike]

Thanks to solve the problem of counting the number of ways to form the target string from the given list of words

[mah-shamim]

Thanks