Number of Ways to Form a Target String Given a Dictionary

Updated on 23 June, 2025
Number of Ways to Form a Target String Given a Dictionary header image

Problem Statement

In this problem, you are provided with a list of strings called words, all of which have the same length. Also, you are given a target string target. Your objective is to determine how many distinct ways you can construct the target string by sequentially selecting characters from the strings in the words.

The process of forming the target is bound by specific rules:

  • You should construct the target from left to right.
  • To construct the ith character of target, you can select the character if it matches exactly in position and value in any of the strings in words.
  • After selecting a character at position k (kth index) from any string, you cannot use any characters from position k or to its left from any string in words.
  • You can use multiple characters from a single string as long as other conditions are respected.

Finally, you need to return the count of different ways to form target modulo 10^9 + 7 as the number may become very large.

Examples

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.

Approach and Intuition

  1. First, parse the provided examples to gain a clear understanding of how target formation rules apply.

    • For instance, given the example where words = ["acca","bbbb","caca"] and target = "aba", the target is formed by successfully matching each character in sequence, considering the condition of not reusing characters from a used index or any index before it.
  2. Conceptualize the problem:

    • Think of the process as moving through each character of the target and exploring all possible characters in the words list that can be used to form it following the constraints.

    • Realize that as you select a character for position i in target, all words are affected as none of their characters from the used index and before can't be used for the next character of target.

  3. Implementation thoughts:

    • Use dynamic programming to keep track of the number of ways to form the target up to each position using valid selections from words, which builds upon previous selections maintaining the validity of rules.

    • Maintain a data structure, like a 2D list where dp[i][j] represents the number of ways to construct the target up to the ith character using the first j characters in any word of words.

  4. Considerations for edge cases:

    • Single character in words and target.
    • No possible formation of target due to constraint limits.
    • The indexing constraint might severely limit the possibilities, needing efficient checking.
  5. Apply mod operation (10^9 + 7) during calculations to handle large numbers, ensuring it doesn’t lead to overflow and adheres to problem constraints.

By understanding and breaking down the problem and examples, you can systematically build an implementation that checks for each character of a target, ensuring the sequence rules are followed accurately, and using dynamic programming for efficient computation of the results.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int waysToForm(vector<string>& wordset, string targetStr) {
        int lenWords = wordset[0].size();
        int lenTarget = targetStr.size();
        const int MODULO = 1000000007;

        // Group frequencies of characters
        vector<vector<int>> freq(lenWords, vector<int>(26, 0));
        for (const string& word : wordset) {
            for (int j = 0; j < lenWords; ++j) {
                freq[j][word[j] - 'a']++;
            }
        }

        // Dynamic programming states
        vector<long> prev(lenTarget + 1, 0);
        vector<long> curr(lenTarget + 1, 0);
        prev[0] = 1;

        // Populate DP table
        for (int i = 1; i <= lenWords; ++i) {
            curr = prev;
            for (int k = 1; k <= lenTarget; ++k) {
                int chIdx = targetStr[k - 1] - 'a';
                curr[k] += (freq[i - 1][chIdx] * prev[k - 1]) % MODULO;
                curr[k] %= MODULO;
            }
            prev = curr;
        }

        return curr[lenTarget];
    }
};

The given C++ solution determines the number of ways to create a target string using a dictionary of available words. The solution employs a dynamic programming approach using frequency counts and moduli to handle large numbers. Here's how the implementation works:

  • Initialize the lengths of the words and the target string.
  • Use the modulo operation to keep calculations manageable and prevent overflow (set to 1,000,000,007).
  • Create a 2D vector to count the frequency of each letter at each position across all wordset words.
  • Iterate through each word in the wordset to populate this frequency table.
  • Use two vectors (prev and curr) to represent the current and previous states in dynamic programming. Begin the prev vector with the base case where the number of ways to form an empty target prefix is 1.
  • Iterate through each position in the words (outer loop) and for each position, compute the number of ways you can form prefixes of the target up to the current length (inner loop).
  • In each iteration, determine the contribution of forming the target using the current letter at the current word position.
  • The final value in curr at the position equal to the length of the target string gives the result which is the total number of ways to form the target string from the dictionary.

This method is efficient in terms of both time and space because it avoids recalculating results for the same subproblems by utilizing dynamic programming and direct access frequency tables.

java
class Solution {

    public int calculateWays(String[] inputWords, String desired) {
        int lenInputWords = inputWords[0].length();
        int lenDesired = desired.length();

        final int MODULO = 1_000_000_007;

        // Calculate the frequency of each character at each position
        int[][] frequency = new int[lenInputWords][26];
        for (String word : inputWords) {
            for (int idx = 0; idx < lenInputWords; idx++) {
                frequency[idx][word.charAt(idx) - 'a']++;
            }
        }

        // Initialize DP arrays for current and previous state.
        long[] prev = new long[lenDesired + 1];
        long[] current = new long[lenDesired + 1];

        // There's exactly one way to form an empty desired string.
        prev[0] = 1;

        // Process each position in the input words.
        for (int i = 1; i <= lenInputWords; i++) {
            // Copy old state to the new state
            System.arraycopy(prev, 0, current, 0, current.length);
            for (int j = 1; j <= lenDesired; j++) {
                // Match current character.
                int charIndex = desired.charAt(j - 1) - 'a';
                current[j] += (frequency[i - 1][charIndex] * prev[j - 1]) % MODULO;
                current[j] %= MODULO;
            }
            System.arraycopy(current, 0, prev, 0, prev.length);
        }

        return (int) prev[lenDesired];
    }
}

The provided code implements a solution to find the number of ways to form a target string using a given dictionary of strings. It uses a dynamic programming approach to efficiently solve the problem through character frequency analysis and state transitions.

  • The calculateWays method takes two parameters: an array of strings inputWords representing the dictionary, and a string desired denoting the target string to form.
  • First, the code calculates the length of the words in the dictionary and the length of the target string.
  • It defines a variable MODULO to ensure the result stays within the integer size limits by applying modulo operations.
  • The frequency of each character at each position in the inputWords is computed and stored in a 2D array frequency.
  • Two dynamic programming (DP) arrays, prev and current, are initialized to track the number of ways to form subsequences up to each length of the desired string.
  • The DP process starts with the base case where forming an empty string has exactly one way.
  • For every position in the input words, it transitions the states based on the frequency of characters matching in desired. The computations incorporate modulo operations to avoid overflow.
  • After processing all characters, the result is stored in prev[lenDesired], indicating the total number of ways to form the target string.

This implementation efficiently computes the result using character frequencies and a dynamic programming approach, leveraging modulo arithmetic to handle large numbers. The approach ensures all possible formations of the desired word are counted, considering all substrings in the inputWords that match the desired sequence.

python
class Solution:
    def countWays(self, words: List[str], target: str) -> int:
        modulus = 1000000007
        num_columns = len(words[0])
        length_target = len(target)
        frequency = [[0] * 26 for _ in range(num_columns)]

        # Calculate frequency of each character at each column position in "words".
        for w in words:
            for idx in range(num_columns):
                frequency[idx][ord(w[idx]) - ord('a')] += 1

        # Using two arrays for dynamic programming: old_dp and new_dp.
        old_dp = [0] * (length_target + 1)
        new_dp = [0] * (length_target + 1)

        # One way to have an empty target.
        old_dp[0] = 1

        # Populate the dp arrays sequentially.
        for column in range(1, num_columns + 1):
            new_dp = old_dp[:]
            for tar_idx in range(1, length_target + 1):
                char_index = ord(target[tar_idx - 1]) - ord('a')

                # Update the number of ways to form the target substring.
                new_dp[tar_idx] += (frequency[column - 1][char_index] * old_dp[tar_idx - 1]) % modulus
                new_dp[tar_idx] %= modulus

            # Prepare dp for next column.
            old_dp = new_dp[:]

        # The solution will be in the last index of old_dp for the full length of target.
        return new_dp[length_target]

This solution addresses the problem of determining the number of ways to form a given target string using a combination of characters from the provided words array, where each word has the same length. This solution utilizes a dynamic programming approach in combination with character frequency analysis in a multi-dimensional array. The process can be summarized as follows:

  • Initialize Constants and Structures:

    • Determine constants such as the length of the target string and the column count from the words array.
    • Create a 2D frequency list where each entry keeps count of characters at specific indices across all words.
  • Character Frequency Calculation:

    • Iterate through each word and each character in the word, updating the frequency matrix accordingly, indicating how often each character appears in each position across all words.
  • Dynamic Programming Array Setup:

    • Define two arrays, old_dp and new_dp, initialized to handle the progress of computing the number of ways to build sub-portions of the target. Start by defining one way to form an empty target.
  • Dynamic Programming Iteration:

    • Iterate through each column represented in the frequency matrix. For each position in the target string, calculate possible combinations by leveraging the frequency of the relevant character at the current column and the previously computed values.
    • Implement modular arithmetic to prevent integer overflows and ensure results match constraints (e.g., modulus = 1000000007).
  • Result Compilation:

    • After processing all columns, the final entry in the new_dp array represents the number of ways to form the entire target string using characters distributed as-per the frequency and position constraints dictated by the provided word array.

This sophisticated method provides an efficient way to solve combination problems constrained by position-specific frequencies, a typical requirement in more advanced string manipulation and dynamic programming challenges.

Comments

No comments yet.