Hard

题目描述

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

你的目标是使用给定的 words 构造 target。从左到右按以下规则构造 target：

  • 为了形成 target[i]（第 i 个字符，下标从 0 开始），你可以从 words[j] 中选择第 k 个字符，前提是 target[i] = words[j][k]
  • 一旦你使用了 words[j] 的第 k 个字符，你就不能再使用 words 中任何字符串的第 x 个字符了，其中 x <= k。也就是说，所有字符串中下标小于等于 k 的字符都不能再使用
  • 重复这个过程直到形成字符串 target

请注意，在满足上述条件的前提下，你可以从同一个字符串中使用多个字符。

返回形成 target 的方案数。由于答案可能很大，请返回对 10^9 + 7 取余的结果。

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

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words 中的所有字符串长度相同
  • 1 <= target.length <= 1000
  • words[i] 和 target 仅包含小写英文字母

解题思路

这是一道经典的动态规划问题。关键在于理解题目的约束条件：一旦使用了某个位置的字符，就不能再使用任何字符串在该位置及其左侧的字符。

解题思路：

  1. 预处理统计：首先统计每个位置上每个字符出现的次数。这样可以快速知道在位置 k 有多少个字符 c。

  2. 动态规划状态定义：设 dp[i][j] 表示使用前 i 个位置的字符，构成 target 前 j 个字符的方案数。

  3. 状态转移：对于每个位置 i 和目标字符位置 j：

    • 不使用位置 i 的字符：dp[i+1][j] += dp[i][j]
    • 使用位置 i 的字符（如果匹配）：dp[i+1][j+1] += dp[i][j] * count[i][target[j]]

  4. 优化空间：由于每一步只依赖前一步的结果，可以使用一维数组优化空间复杂度。

时间复杂度分析：

  • 预处理：O(words.length × word.length)
  • 动态规划：O(word.length × target.length)
  • 总体：O(words.length × word.length + word.length × target.length)

代码实现

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        const int MOD = 1000000007;
        int m = words[0].length();
        int n = target.length();
        
        // 统计每个位置每个字符的出现次数
        vector<vector<int>> count(m, vector<int>(26, 0));
        for (const string& word : words) {
            for (int i = 0; i < m; i++) {
                count[i][word[i] - 'a']++;
            }
        }
        
        // dp[j] 表示构成target前j个字符的方案数
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        
        for (int i = 0; i < m; i++) {
            // 从后往前更新，避免重复使用
            for (int j = min(i + 1, n); j > 0; j--) {
                int ch = target[j - 1] - 'a';
                dp[j] = (dp[j] + dp[j - 1] * count[i][ch]) % MOD;
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 10**9 + 7
        m = len(words[0])
        n = len(target)
        
        # 统计每个位置每个字符的出现次数
        count = [[0] * 26 for _ in range(m)]
        for word in words:
            for i, ch in enumerate(word):
                count[i][ord(ch) - ord('a')] += 1
        
        # dp[j] 表示构成target前j个字符的方案数
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(m):
            # 从后往前更新，避免重复使用
            for j in range(min(i + 1, n), 0, -1):
                ch_idx = ord(target[j - 1]) - ord('a')
                dp[j] = (dp[j] + dp[j - 1] * count[i][ch_idx]) % MOD
        
        return dp[n]

public class Solution {
    public int NumWays(string[] words, string target) {
        const int MOD = 1000000007;
        int m = words[0].Length;
        int n = target.Length;
        
        // 统计每个位置每个字符的出现次数
        int[,] count = new int[m, 26];
        foreach (string word in words) {
            for (int i = 0; i < m; i++) {
                count[i, word[i] - 'a']++;
            }
        }
        
        // dp[j] 表示构成target前j个字符的方案数
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 0; i < m; i++) {
            // 从后往前更新，避免重复使用
            for (int j = Math.Min(i + 1, n); j > 0; j--) {
                int chIdx = target[j - 1] - 'a';
                dp[j] = (dp[j] + dp[j - 1] * count[i, chIdx]) % MOD;
            }
        }
        
        return (int)dp[n];
    }
}

var numWays = function(words, target) {
    const MOD = 1000000007;
    const m = words[0].length;
    const n = target.length;
    
    // 统计每个位置每个字符的出现次数
    const count = Array(m).fill().map(() => Array(26).fill(0));
    for (const word of words) {
        for (let i = 0; i < m; i++) {
            count[i][word.charCodeAt(i) - 97]++;
        }
    }
    
    // dp[j] 表示构成target前j个字符的方案数
    const dp = Array(n + 1).fill(0);
    dp[0] = 1;
    
    for (let i = 0; i < m; i++) {
        // 从后往前更新，避免重复使用
        for (let j = Math.min(i + 1, n); j > 0; j--) {
            const chIdx = target.charCodeAt(j - 1) - 97;
            dp[j] = (dp[j] + dp[j - 1] * count[i][chIdx]) % MOD;
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(words.length × word.length + word.length × target.length)
空间复杂度O(word.length × 26 + target.length) = O(word.length + target.length)