Number of Ways to Form a Target String Given a Dictionary

Number of Ways to Form a Target String Given a Dictionary - Problem

You are given a list of strings words of the same length 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 i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
Once you use the k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusable 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: 6 ways to form 'aba': use 'a' from position 0, 'b' from position 1, 'a' from position 2. Multiple combinations possible due to multiple words containing required characters.

Example 2 — No Solution

$ Input: words = ["abcd"], target = "abce"

› Output: 0

💡 Note: Cannot form 'abce' because there's no 'e' in any word, so it's impossible to complete the target string.

Example 3 — Single Character

$ Input: words = ["abab","baba"], target = "a"

› Output: 4

💡 Note: Can choose 'a' from position 0 or position 2, and from either word, giving us 2×2 = 4 ways total.

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

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to use dynamic programming with character frequency counting. Once a position is used, all earlier positions become unavailable across all words. The optimal approach uses a 2D DP table where dp[i][j] represents ways to form first i characters of target using first j word positions. Time: O(m×n), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(m × n)	O(m × n)	Add memoization to brute force to avoid recalculating same states
Bottom-Up Dynamic Programming	O(m × n)	O(m × n)	Build solution iteratively using 2D DP table with character frequency optimization
Brute Force Recursion	O(2^(m+n))	O(m+n)	Try all possible ways to select characters recursively

Memoized Recursion — Algorithm Steps

Use recursion with memoization cache
Cache results for each (target_index, word_position) state
Return cached result if state was computed before

Visualization

Tap to expand

Step-by-Step Walkthrough

Frequency Count

Count character occurrences at each position

Recursive DP

Use memoization to cache results for each state

Optimized

Each state computed only once, dramatically faster

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;

int memo[1001][1001];
int freq[1001][26];
int m, n;

int dp(int targetIdx, int wordPos, char* target) {
    if (targetIdx == n) return 1;
    if (wordPos == m) return 0;
    
    if (memo[targetIdx][wordPos] != -1) return memo[targetIdx][wordPos];
    
    long long ways = dp(targetIdx, wordPos + 1, target);
    
    int targetChar = target[targetIdx] - 'a';
    int charCount = freq[wordPos][targetChar];
    if (charCount > 0) {
        ways += (long long)charCount * dp(targetIdx + 1, wordPos + 1, target);
    }
    
    ways %= MOD;
    return memo[targetIdx][wordPos] = ways;
}

int solution(char words[][1001], int wordCount, char* target) {
    m = strlen(words[0]);
    n = strlen(target);
    
    memset(memo, -1, sizeof(memo));
    memset(freq, 0, sizeof(freq));
    
    for (int i = 0; i < wordCount; i++) {
        for (int j = 0; j < m; j++) {
            freq[j][words[i][j] - 'a']++;
        }
    }
    
    return dp(0, 0, target);
}

int main() {
    char words[1000][1001];
    char target[1001];
    int wordCount = 0;
    
    char line[10001];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL) {
        if (strlen(token) > 0) {
            strcpy(words[wordCount], token);
            wordCount++;
        }
        token = strtok(NULL, "[],\"\n ");
    }
    
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    int result = solution(words, wordCount, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Each state (target_index, word_position) computed at most once

✓ Linear Growth

Space Complexity

O(m × n)

Memoization cache stores results for m×n states plus recursion stack

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler