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

By /

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.

Approach 01:

class Solution {
public:
    int targetLength;
    int wordLength;
    const int MOD = 1e9+7;
    int memo[1001][1001];
    
    int solve(int targetIndex, int columnIndex, vector<vector<long long>>& charFrequency, string &target) {
        if (targetIndex == targetLength) // Completed target formation
            return 1;
        if (columnIndex == wordLength) // Exhausted all columns
            return 0;
        if (memo[targetIndex][columnIndex] != -1) // Return memoized result
            return memo[targetIndex][columnIndex];
        
        // Option 1: Skip current column
        int skipColumn = solve(targetIndex, columnIndex + 1, charFrequency, target) % MOD;
        
        // Option 2: Use current column
        int useColumn = (charFrequency[target[targetIndex] - 'a'][columnIndex] * 
                         solve(targetIndex + 1, columnIndex + 1, charFrequency, target)) % MOD;
        
        return memo[targetIndex][columnIndex] = (skipColumn + useColumn) % MOD;
    }
    
    int numWays(vector<string>& words, string target) {
        wordLength = words[0].size();
        targetLength = target.length();
        
        // Build frequency table for each character at every column
        vector<vector<long long>> charFrequency(26, vector<long long>(wordLength, 0));
        for (int column = 0; column < wordLength; column++) {
            for (string &word : words) {
                charFrequency[word[column] - 'a'][column]++;
            }
        }
        
        // Initialize memoization table
        memset(memo, -1, sizeof(memo));
        return solve(0, 0, charFrequency, target);
    }
};
class Solution:
    MOD = int(1e9+7)
    
    def __init__(self):
        self.memo = []
        self.targetLength = 0
        self.wordLength = 0
    
    def solve(self, targetIndex, columnIndex, charFrequency, target):
        if targetIndex == self.targetLength:  # Completed target formation
            return 1
        if columnIndex == self.wordLength:  # Exhausted all columns
            return 0
        if self.memo[targetIndex][columnIndex] != -1:  # Return memoized result
            return self.memo[targetIndex][columnIndex]
        
        # Option 1: Skip current column
        skipColumn = self.solve(targetIndex, columnIndex + 1, charFrequency, target) % self.MOD
        
        # Option 2: Use current column
        useColumn = (charFrequency[ord(target[targetIndex]) - ord('a')][columnIndex] * 
                     self.solve(targetIndex + 1, columnIndex + 1, charFrequency, target)) % self.MOD
        
        self.memo[targetIndex][columnIndex] = (skipColumn + useColumn) % self.MOD
        return self.memo[targetIndex][columnIndex]
    
    def numWays(self, words, target):
        self.wordLength = len(words[0])
        self.targetLength = len(target)
        
        # Build frequency table for each character at every column
        charFrequency = [[0] * self.wordLength for _ in range(26)]
        for column in range(self.wordLength):
            for word in words:
                charFrequency[ord(word[column]) - ord('a')][column] += 1
        
        # Initialize memoization table
        self.memo = [[-1] * self.wordLength for _ in range(self.targetLength)]
        return self.solve(0, 0, charFrequency, target)

Time Complexity

  • Building Character Frequency Table:
    • Iterating over each column of words, for a total of \( O(w \cdot l) \), where \( w \) is the number of words and \( l \) is the length of each word.
  • Recursive Function with Memoization:
    • The function solve is called with a maximum of \( O(targetLength \cdot wordLength) \) states due to the memoization table.
    • Each state computation involves constant work, making it \( O(targetLength \cdot wordLength) \).
  • Overall Time Complexity:

    The total time complexity is:
    \( O(w \cdot l + targetLength \cdot wordLength) \).

Space Complexity

  • Character Frequency Table:
    • The space required for storing the frequency of each character in each column is \( O(26 \cdot wordLength) \).
  • Memoization Table:
    • The memoization table stores results for \( O(targetLength \cdot wordLength) \) states, requiring \( O(targetLength \cdot wordLength) \) space.
  • Auxiliary Space:
    • The recursive stack depth is \( O(targetLength) \), corresponding to the target length.
  • Overall Space Complexity:

    The total space complexity is: \( O(26 \cdot wordLength + targetLength \cdot wordLength + targetLength) \), which simplifies to \( O(targetLength \cdot wordLength) \) as the dominant term.

Approach 01:

class Solution {
public:
    const int MOD = 1e9+7;
    int numWays(vector<string>& words, string target) {
        int wordLength = words[0].size();
        int targetLength = target.length();
        
        // Build frequency table for each character at every column
        vector<vector<long long>> charFrequency(26, vector<long long>(wordLength, 0));
        for (int column = 0; column < wordLength; column++) {
            for (string &word : words) {
                charFrequency[word[column] - 'a'][column]++;
            }
        }
        
        // dp[targetLength][columnLength]: Total ways to form target of length targetLength using columnLength columns
        vector<vector<long long>> dp(targetLength + 1, vector<long long>(wordLength + 1, 0));
        dp[0][0] = 1; // Base case: 1 way to form empty target
        
        for (int targetIndex = 0; targetIndex <= targetLength; targetIndex++) {
            for (int columnIndex = 0; columnIndex <= wordLength; columnIndex++) {
                // Skip current column
                if (columnIndex < wordLength)
                    dp[targetIndex][columnIndex + 1] = (dp[targetIndex][columnIndex + 1] + dp[targetIndex][columnIndex]) % MOD;
                
                // Use current column
                if (targetIndex < targetLength && columnIndex < wordLength) {
                    dp[targetIndex + 1][columnIndex + 1] = (dp[targetIndex + 1][columnIndex + 1] + 
                        charFrequency[target[targetIndex] - 'a'][columnIndex] * dp[targetIndex][columnIndex]) % MOD;
                }
            }
        }
        return dp[targetLength][wordLength];
    }
};
class Solution:
    MOD = int(1e9+7)
    
    def numWays(self, words, target):
        wordLength = len(words[0])
        targetLength = len(target)
        
        # Build frequency table for each character at every column
        charFrequency = [[0] * wordLength for _ in range(26)]
        for column in range(wordLength):
            for word in words:
                charFrequency[ord(word[column]) - ord('a')][column] += 1
        
        # dp[targetLength][columnLength]: Total ways to form target of length targetLength using columnLength columns
        dp = [[0] * (wordLength + 1) for _ in range(targetLength + 1)]
        dp[0][0] = 1  # Base case: 1 way to form empty target
        
        for targetIndex in range(targetLength + 1):
            for columnIndex in range(wordLength + 1):
                # Skip current column
                if columnIndex < wordLength:
                    dp[targetIndex][columnIndex + 1] = (dp[targetIndex][columnIndex + 1] + dp[targetIndex][columnIndex]) % self.MOD
                
                # Use current column
                if targetIndex < targetLength and columnIndex < wordLength:
                    dp[targetIndex + 1][columnIndex + 1] = (dp[targetIndex + 1][columnIndex + 1] + 
                        charFrequency[ord(target[targetIndex]) - ord('a')][columnIndex] * dp[targetIndex][columnIndex]) % self.MOD
        
        return dp[targetLength][wordLength]

Time Complexity

  • Building Character Frequency Table:
    • Iterating over each column of words, for a total of \( O(w \cdot l) \), where \( w \) is the number of words and \( l \) is the length of each word.
  • Dynamic Programming Table Updates:
    • The outer loop iterates over \( targetLength + 1 \) states.
    • The inner loop iterates over \( wordLength + 1 \) states.
    • Each state computation is \( O(1) \), resulting in \( O(targetLength \cdot wordLength) \).
  • Overall Time Complexity:

    The total time complexity is: \( O(w \cdot l + targetLength \cdot wordLength) \).

Space Complexity

  • Character Frequency Table:
    • The space required for storing the frequency of each character in each column is \( O(26 \cdot wordLength) \).
  • Dynamic Programming Table:
    • The table requires \( O((targetLength + 1) \cdot (wordLength + 1)) \) space.
  • Overall Space Complexity:

    The total space complexity is: \( O(26 \cdot wordLength + targetLength \cdot wordLength) \), which simplifies to \( O(targetLength \cdot wordLength) \) as the dominant term.

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top