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

🔗 https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary

题目

• 给一个字符串数组 words，字符串的长度都一样，给一个目标字符串 target
• 返回由字符串组，基于规则组成的 target 的组合数，mod 10^9 + 7
• 规则如下：
  • target 只能 from left to right 逐个形成
  • 每一轮形成 target[i] == words[x][j] 时，下一轮只能取 j +1 起的字符串

思路

• 二维 dp[i][j]，表达的含义为，形成 target i 字符，取 words 中最大的 index 为 j 时，可以有的组合数
• 答案就是 dp[target.size() -1][words[0].size() -1]
• 该组合的形成有两种来源：
  • target i 字符由 words 最大 index j-1 形成
  • target i 字符由 words 最大 index j 形成，即当前 index j == target i 的个数，组合乘以 dp[i-1][j-1]
• 初始化时，dp[0][…] 都为 1

代码

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        long long  mod = 1000000000 + 7;
        long long  dp[1010][1010];
        memset(dp, 0, sizeof dp);
        unordered_map<char, int> word_map[1010];
        for (int i = 0; i < words[0].size(); i++) {
            for (int j = 0; j < words.size(); j++) {
                word_map[i][words[j][i]]++;
            }
        }
        for (int i = 0; i < target.size(); i++) {
            int x_max = words[0].size() - target.size() + i + 1;
            for (int j = i; j < x_max; j++) {
                if (i == 0) dp[i][j] = 1;
                dp[i+1][j+1] = dp[i+1][j];
                int count = word_map[j][target[i]];
                if (count != 0) {
                    dp[i + 1][j + 1] += ((dp[i][j] * count) % mod);
                    dp[i + 1][j + 1] %= mod;
                }
            }
        }

        return dp[target.size()][words[0].size()];
    }
};