Number of Ways to Form a Target String Given a Dictionary

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        const int MOD = 1'000'000'007;
        int L = words[0].size(), T = target.size();
        vector<vector<int>> freq(26, vector<int>(L, 0));
        for (auto& w : words)
            for (int c = 0; c < L; ++c)
                ++freq[w[c] - 'a'][c];
        vector<long long> dp(T + 1, 0);
        dp[0] = 1;
        for (int c = 0; c < L; ++c) {
            for (int j = T; j >= 1; --j) {
                dp[j] = (dp[j] + dp[j - 1] * freq[target[j - 1] - 'a'][c]) % MOD;
            }
        }
        return (int)dp[T];
    }
};

func numWays(words []string, target string) int {
    const MOD = 1_000_000_007
    L, T := len(words[0]), len(target)
    freq := make([][]int, 26)
    for i := range freq {
        freq[i] = make([]int, L)
    }
    for _, w := range words {
        for c := 0; c < L; c++ {
            freq[w[c]-'a'][c]++
        }
    }
    dp := make([]int64, T+1)
    dp[0] = 1
    for c := 0; c < L; c++ {
        for j := T; j >= 1; j-- {
            dp[j] = (dp[j] + dp[j-1]*int64(freq[target[j-1]-'a'][c])) % MOD
        }
    }
    return int(dp[T])
}

from typing import List

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 1_000_000_007
        L, T = len(words[0]), len(target)
        freq = [[0] * L for _ in range(26)]
        for w in words:
            for c in range(L):
                freq[ord(w[c]) - ord('a')][c] += 1
        dp = [0] * (T + 1)
        dp[0] = 1
        for c in range(L):
            for j in range(T, 0, -1):
                dp[j] = (dp[j] + dp[j - 1] * freq[ord(target[j - 1]) - ord('a')][c]) % MOD
        return dp[T]

function numWays(words, target) {
    const MOD = 1_000_000_007n;
    const L = words[0].length, T = target.length;
    const freq = Array.from({ length: 26 }, () => new Array(L).fill(0));
    for (const w of words) {
        for (let c = 0; c < L; c++) {
            freq[w.charCodeAt(c) - 97][c]++;
        }
    }
    const dp = new Array(T + 1).fill(0n);
    dp[0] = 1n;
    for (let c = 0; c < L; c++) {
        for (let j = T; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1] * BigInt(freq[target.charCodeAt(j - 1) - 97][c])) % MOD;
        }
    }
    return Number(dp[T]);
}

class Solution {
    public int numWays(String[] words, String target) {
        final int MOD = 1_000_000_007;
        int L = words[0].length(), T = target.length();
        int[][] freq = new int[26][L];
        for (String w : words) {
            for (int c = 0; c < L; c++) {
                freq[w.charAt(c) - 'a'][c]++;
            }
        }
        long[] dp = new long[T + 1];
        dp[0] = 1;
        for (int c = 0; c < L; c++) {
            for (int j = T; j >= 1; j--) {
                dp[j] = (dp[j] + dp[j - 1] * freq[target.charAt(j - 1) - 'a'][c]) % MOD;
            }
        }
        return (int) dp[T];
    }
}

function numWays(words: string[], target: string): number {
    const MOD = 1_000_000_007n;
    const L = words[0].length, T = target.length;
    const freq: number[][] = Array.from({ length: 26 }, () => new Array(L).fill(0));
    for (const w of words) {
        for (let c = 0; c < L; c++) {
            freq[w.charCodeAt(c) - 97][c]++;
        }
    }
    const dp: bigint[] = new Array(T + 1).fill(0n);
    dp[0] = 1n;
    for (let c = 0; c < L; c++) {
        for (let j = T; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1] * BigInt(freq[target.charCodeAt(j - 1) - 97][c])) % MOD;
        }
    }
    return Number(dp[T]);
}