We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Form a Target String Given a Dictionary

Difficulty: Hard

Problem Description

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 specific rules, such as forming target from left to right, choosing characters from words, and making certain characters unusable as you progress. Return the number of ways to form target from words, modulo 10^9 + 7.

Key Insights

  • The problem requires careful tracking of character usage to ensure no character is reused incorrectly.
  • Dynamic programming can be employed to count the number of ways to form the target string character by character.
  • A frequency count of characters in words can be utilized to efficiently determine how many choices are available at each step.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the target and m is the number of words. Space Complexity: O(m), used for storing character frequencies for each position.

Solution

To solve the problem, we can use a dynamic programming approach. We will maintain a list to store the number of ways to form the target up to each position. For each character in the target, we will calculate how many ways we can match it using the characters available in words while respecting the constraints of character usage.

  1. Initialize a list to keep track of the number of ways to form the target.
  2. For each character in the target, check all characters in the words to see if they can match.
  3. Update the count of ways using the frequency of valid characters from previous positions.
  4. Return the total ways after processing the entire target.

Code Solutions

def numWays(words, target):
    MOD = 10**9 + 7
    m, n = len(words), len(target)
    
    # Initialize a frequency array for each character in target
    freq = [0] * 26
    for word in words:
        for j in range(len(word)):
            freq[ord(word[j]) - ord('a')] += 1
    
    # DP array to count the ways
    dp = [0] * (n + 1)
    dp[0] = 1  # There's one way to form the empty target
    
    for i in range(n):
        current_char_index = ord(target[i]) - ord('a')
        current_char_count = freq[current_char_index]
        for j in range(i + 1, 0, -1):
            dp[j] = (dp[j] + dp[j - 1] * current_char_count) % MOD
            
    return dp[n]
← Back to All Questions