Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

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

My accepted C++ solution to LeetCode problem 1744, Number of Ways to Form a Target String Given a Dictionary, running in 36ms.

  • Difficulty: Hard
  • C++
  • Runtime 36ms
  • Memory 34MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

C++

Accepted on LeetCode — runtime 36ms, memory 34MB, accepted 2025-12-27.

cpp
class Solution {
    public:
    int numWays(vector<string>& words, string target) {
        const int MOD = 1e9 + 7;
        int m = words[0].size(), n = target.size();
        vector<vector<long long>> cnt(m, vector<long long>(26, 0));
        for (auto& w : words)
        for (int i = 0; i < m; i++) cnt[i][w[i] - 'a']++;
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = min(i + 1, n); j >= 1; j--) {
                dp[j] = (dp[j] + dp[j - 1] * cnt[i][target[j - 1] - 'a']) % MOD;
            }
        }
        return dp[n];
    }
};

Source