最适合穷人开的店_南宁seo规则_最近新闻_网站点击量软件

🔗 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()];}
};