通过给定词典构造目标字符串的方案数

1639. 通过给定词典构造目标字符串的方案数

给你一个字符串列表 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 的方案数。由于答案可能会很大，请对 10⁹ + 7 取余后返回。

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

示例 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

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int numWays(vector<string>& words, string target) { } };

python3 解法, 执行用时: 1812 ms, 内存消耗: 176.4 MB, 提交时间: 2023-10-27 22:09:26

class Solution:
    def numWays1(self, words: List[str], target: str) -> int:
        n=len(words[0])
        m=len(words)
        dic_lst=[Counter([words[i][k] for i in range(m)]) for k in range(n)]
        t=len(target)
        dp=[[0]*t for i in range(n)]
        cur=0
        for i in range(n):
            if target[0] in dic_lst[i]:
                cur+=dic_lst[i][target[0]]
            dp[i][0]=cur
        for i in range(1,n):
            for k in range(1,t):
                if target[k] in dic_lst[i]:
                    dp[i][k]=dic_lst[i][target[k]]*dp[i-1][k-1]+dp[i-1][k]
                else:
                    dp[i][k]=dp[i-1][k]
        return dp[-1][-1]%(10**9+7)

    def numWays(self, words: List[str], target: str) -> int:
        mod = 10 ** 9 + 7
        m,n = len(words[0]),len(target)
        
        # 存储每列上的元素个数
        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]
      
        @lru_cache(None)
        def dfs(index,k):
            if index == n:
                return 1
            if k == m:
                return 0
            res = dfs(index,k + 1)
            if target[index] in index_count[k]:
                res += index_count[k][target[index]] * dfs(index + 1,k + 1)
            return res
        
        return dfs(0,0) % mod

golang 解法, 执行用时: 48 ms, 内存消耗: 8.5 MB, 提交时间: 2023-10-27 22:08:23

func numWays(words []string, target string) int {
	m, n := len(words[0]), len(target)
	ws := make([][26]int, m)
	for i := 0; i < len(words); i++ {
		for j := 0; j < m; j++ {
			ws[j][words[i][j]-'a']++
		}
	}
	dp := make([]int, n+1)
	dp1 := make([]int, n+1)
	dp[0] = 1
	dp1[0]=1
	for i := 0; i < m; i++ {
		copy(dp1, dp)
		for j := 1; j <= n; j++ {
			dp1[j] += dp[j-1] * ws[i][target[j-1]-'a']
			dp1[j] %= 1e9 + 7
		}
		dp,dp1 = dp1,dp
	}
	return dp[n]
}

java 解法, 执行用时: 50 ms, 内存消耗: 48.3 MB, 提交时间: 2023-10-27 22:07:40

class Solution {
    public static final int MOD = (int)1e9+7;
    public int numWays(String[] words, String target) {
        // words中单词的长度
        int n = words[0].length();
        // target的长度
        int m = target.length();

        int[][] cnt = new int[n][26];

        for(String word:words) {
            for(int i = 0;i < n;i ++) {
                cnt[i][word.charAt(i)-'a'] ++; 
            }
        }
        long[] f = new long[m+1];

        f[0] = 1;
        
        for(int i = 1;i <= n;i ++) {
            for(int j = m;j >= 1;j --) {
                // f[i][j] = f[i-1][j] + f[i-1][j-1]
                f[j] = (f[j] + f[j-1]*cnt[i-1][target.charAt(j-1)-'a']%MOD)%MOD;
            }
            
        }

        return (int)f[m];
    }
}

cpp 解法, 执行用时: 148 ms, 内存消耗: 77.6 MB, 提交时间: 2023-10-27 22:07:14

class Solution {
public:
    const int mod = 1e9+7;
    long dfs(vector<vector<long>>& dp, vector<vector<int>>& cnt, string& target, int i, int j, int n, int m) {
        if (j == m) return 1;
        if (n - i < m - j) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        
        long val = cnt[i][target[j] - 'a'] * dfs(dp, cnt, target, i + 1, j + 1, n, m);
        val += dfs(dp, cnt, target, i + 1, j, n, m);
        val %= mod;
        return dp[i][j] = val;
    }
    
    
    int numWays(vector<string>& words, string target) {
        int n = words[0].length();
        //  cnt[i][ch] 表示在所有单词的第 i 个字符中，字符 ch 出现的次数。
        vector<vector<int>> cnt(n, vector<int>(26, 0));
        for (const auto& s: words) {
            for (int i = 0; i < n; i++) {
                cnt[i][s[i]-'a']++;
            }
        }
        
        int m = target.length();
        // dp[i][j] 表示以 words[i..] 为字典，构造字符串 target[j..] 的方案数
        vector<vector<long>> dp(n, vector<long>(m, -1));
        return dfs(dp, cnt, target, 0, 0, n, m);
    }
};

上一题

下一题