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

标签: 数组 字符串 动态规划

难度: Hard

给你一个字符串列表 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 的方案数。由于答案可能会很大，请对 109 + 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 都仅包含小写英文字母。

Submission

运行时间: 444 ms

内存: 50.2 MB

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        n,m=len(words[0]),len(target)
        graph=[defaultdict(int) for _ in range(n)]
        #预处理一下,建图计数预处理
        for x in words:
            for i in range(n):
                graph[i][x[i]]+=1
        #graph[i][j]模式串下标为i,且字符为j的个数
        MOD=10**9+7
        #dfs(i,j)表示当前构造到target的下标i的字符,且从模式串的下标j开始使用的方案数
        @cache
        def dfs(i,j):
            if i==m:
                return 1
            elif n-j<m-i:
                return 0
            #可以跳过当前下标
            ch=target[i]
            return (dfs(i,j+1)+graph[j][ch]*dfs(i+1,j+1))%MOD
        return dfs(0,0)

Explain

题解采用了动态规划的策略结合记忆化搜索，首先通过统计每个words中每个位置的字符出现频次来进行预处理，建立一个图（graph），其中graph[i][char]表示在words中所有字符串的第i个位置上字符char出现的次数。接着使用深度优先搜索（DFS）配合记忆化，定义dfs(i, j)为从target的第i个字符开始，尝试匹配words中从第j个位置开始的字符所产生的方案数。如果当前位置的字符可以匹配，则方案数为选择当前字符与跳过当前字符方案数之和。为了优化，如果剩余的words长度不足以匹配剩下的target，则直接返回0。最终，返回dfs(0, 0)即为结果。

时间复杂度: O(k*n + m*n)

空间复杂度: O(m*n + n)

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        n, m = len(words[0]), len(target)
        graph = [defaultdict(int) for _ in range(n)]
        # 预处理，统计每个位置的字符出现频率
        for x in words:
            for i in range(n):
                graph[i][x[i]] += 1
        MOD = 10**9 + 7
        @cache
        def dfs(i, j):
            # 如果已经匹配完target
            if i == m:
                return 1
            # 如果剩余的words长度不足以匹配剩下的target
            elif n - j < m - i:
                return 0
            ch = target[i]
            # 递归计算跳过当前字符或者匹配当前字符的方案数
            return (dfs(i, j + 1) + graph[j][ch] * dfs(i + 1, j + 1)) % MOD
        return dfs(0, 0)

Explore

题解中通过动态规划的方式来确保不违反这一规则。动态规划函数dfs(i, j)从target的第i个字符开始考虑，从words的第j个位置开始尝试匹配，这意味着当从words的第j位置尝试匹配时，自然不会再考虑第j位置之前的字符。每次递归调用dfs(i+1, j+1)都将i和j同时递增，这保证了一旦使用了words中某字符串的第j个位置的字符后，就不会再使用该字符串的第j位置之前的字符，从而满足题目的要求。

这个逻辑基于对问题所需条件的理解。如果在位置j处，剩余的words长度（即n-j）小于target剩余需要匹配的长度（即m-i），则不可能再形成有效匹配。因为每个target字符至少需要一个对应的words字符来匹配，如果words剩余的长度不足以为每个剩余的target字符提供一个匹配字符，就无法构成有效的匹配方案。因此，在这种情况下直接返回0是合理的，表示不存在有效的匹配方案。

在构建graph的过程中，首先初始化一个长度等于words中字符串长度的列表，列表中的每个元素是一个字典，用于存储每个位置字符的出现次数。然后遍历words中的每个字符串，对于每个字符串的每个字符，更新对应位置的字典，记录该字符出现的次数。这样，graph[i][char]最终存储的是在words中所有字符串的第i个位置字符char出现的总次数。这种预处理方式保证了在后续的深度优先搜索中能够快速获取任何位置上任何字符的出现频率。

在递归过程中，使用记忆化可以避免重复计算已经解决的子问题，从而大大提高算法的效率。由于在不同的递归调用中，相同的(i, j)参数对可能会多次出现，如果不使用记忆化，则每次都需要重新计算dfs(i, j)的结果，这将导致大量的重复计算和不必要的时间消耗。记忆化通过存储这些子问题的解（如使用装饰器@cache），确保每个子问题只计算一次，当再次遇到相同的子问题时，可以直接使用已经计算好的结果。