算法leetcode

【DP难题】力扣1639-通过给定词典构造目标字符串的方案数

字数统计: 1.3k字   |   阅读时长: 6分
, ,

摘要: 一道推公式优化 DP 的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们看一个推公式优化 DP 的问题。本题是第 37 双周赛 D 题。关于推公式优化 DP 的更多例子，参考文章 推公式优化DP。

$1 题目

给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同 。

你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：

  • 从左到右依次构造 target 的每一个字符。
  • 为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
  • 一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。
  • 请你重复此过程直到得到目标字符串 target 。

请注意， 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。

请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 1e9 + 7 取余 后返回。

（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

提示：

1
2
3
4
5
1 <= words.length <= 1000
1 <= words[i].length <= 1000
words 中所有单词长度相同。
1 <= target.length <= 1000
words[i] 和 target 都仅包含小写英文字母。

示例 1：
输入：words = [“acca”,”bbbb”,”caca”], target = “aba”
输出：6
解释：总共有 6 种方法构造目标串。
“aba” -> 下标为 0 (“acca”)，下标为 1 (“bbbb”)，下标为 3 (“caca”)
“aba” -> 下标为 0 (“acca”)，下标为 2 (“bbbb”)，下标为 3 (“caca”)
“aba” -> 下标为 0 (“acca”)，下标为 1 (“bbbb”)，下标为 3 (“acca”)
“aba” -> 下标为 0 (“acca”)，下标为 2 (“bbbb”)，下标为 3 (“acca”)
“aba” -> 下标为 1 (“caca”)，下标为 2 (“bbbb”)，下标为 3 (“acca”)
“aba” -> 下标为 1 (“caca”)，下标为 2 (“bbbb”)，下标为 3 (“caca”)

示例 2：
输入：words = [“abba”,”baab”], target = “bab”
输出：4
解释：总共有 4 种不同形成 target 的方法。
“bab” -> 下标为 0 (“baab”)，下标为 1 (“baab”)，下标为 2 (“abba”)
“bab” -> 下标为 0 (“baab”)，下标为 1 (“baab”)，下标为 3 (“baab”)
“bab” -> 下标为 0 (“baab”)，下标为 2 (“baab”)，下标为 3 (“baab”)
“bab” -> 下标为 1 (“abba”)，下标为 2 (“baab”)，下标为 3 (“baab”)

示例 3：
输入：words = [“abcd”], target = “abcd”
输出：1

示例 4：
输入：words = [“abab”,”baba”,”abba”,”baab”], target = “abba”
输出：16

$2 题解

动态规划

mappings[j] 为第 j 列的字符计数。

1
2
3
4
5
6
7
8
9
10
dp[i][k] := 构造 t[i..n-1], 词典可以用 [k..L-1] 这些列时的方案数

初始化
i == n: dp[i][...] = 1
k == L: dp[...][k] = 0 (i < n)
剪枝: n - i > L - k: dp[i][k] = 0

转移
dp[i][k] = sum(dp[i+1][j+1] * mapping[j][t[i]]) 
    其中 k <= j <= L - 1 且 mapping[j][t[i]] > 0

代码 (C++)

注：$O(NL^{2})$ 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int n = target.size();
        int L = words[0].size();
        mappings.assign(L, unordered_map<int, int>());
        for(const string &s: words)
            for(int j = 0; j < L; ++j)
                ++mappings[j][s[j]];
        dp.assign(n, vector<int>(L, -1));
        return solve(target, 0, 0);
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
    vector<unordered_map<int, int>> mappings;
    vector<vector<int>> dp;

    int solve(const string& t, int i, int k)
    {
        int n = t.size(), L = mappings.size();
        if(i == n)
            return 1;
        if(k == L)
            return 0;
        if(dp[i][k] != -1)
            return dp[i][k];

        dp[i][k] = 0;
        for(int j = k; j < L; ++j)
        {
            if(mappings[j].count(t[i]) > 0)
            {
                dp[i][k] = ((ll)dp[i][k] + (ll)mappings[j][t[i]] * solve(t, i + 1, j + 1)) % MOD;
            }
        }
        return dp[i][k];
    }
};

推公式优化

代码 (C++)

$O(NL)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int n = target.size();
        int L = words[0].size();
        mappings.assign(L, unordered_map<int, int>());
        for(const string &s: words)
            for(int j = 0; j < L; ++j)
                ++mappings[j][s[j]];
        dp.assign(n, vector<int>(L, -1));
        return solve(target, 0, 0);
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
    vector<unordered_map<int, int>> mappings;
    vector<vector<int>> dp;

    int solve(const string& t, int i, int k)
    {
        int n = t.size(), L = mappings.size();
        if(i == n)
            return 1;
        if(k == L)
            return 0;
        if(n - i > L - k)
            return 0;
        if(dp[i][k] != -1)
            return dp[i][k];

        dp[i][k] = solve(t, i, k + 1);
        if(mappings[k].count(t[i]) > 0)
            dp[i][k] = (dp[i][k] + (ll)solve(t, i + 1, k + 1) * mappings[k][t[i]]) % MOD;
        return dp[i][k];
    }
};
Share