Hard

题目描述

给你一个字符串 target，一个字符串数组 words，和一个整数数组 costs，两个数组长度相同。

想象一个空字符串 s。

你可以执行以下操作任意次（包括零次）：

  • 选择一个在范围 [0, words.length - 1] 内的索引 i。
  • 将 words[i] 追加到 s。
  • 操作的代价是 costs[i]。

返回使 s 等于 target 的最小代价。如果不可能，返回 -1。

示例 1：

输入：target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
输出：7
解释：
可以通过以下操作实现最小代价：
- 选择索引 1，将 "abc" 追加到 s，代价为 1，得到 s = "abc"。
- 选择索引 2，将 "d" 追加到 s，代价为 1，得到 s = "abcd"。  
- 选择索引 4，将 "ef" 追加到 s，代价为 5，得到 s = "abcdef"。

示例 2：

输入：target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
输出：-1
解释：
无法使 s 等于 target，所以返回 -1。

约束条件：

  • 1 <= target.length <= 5 * 10^4
  • 1 <= words.length == costs.length <= 5 * 10^4
  • 1 <= words[i].length <= target.length
  • words[i].length 的总和不超过 5 * 10^4
  • target 和 words[i] 只包含小写英文字母
  • 1 <= costs[i] <= 10^4

解题思路

这是一个典型的动态规划问题，可以用多种方法解决：

解法分析

方法一：DP + 哈希（推荐）

使用动态规划，dp[i] 表示构造 target[0...i-1] 的最小代价。对于每个位置，我们检查所有可能的单词匹配。

为了优化匹配效率，我们可以将所有单词存储在哈希表中，并按长度分组。这样可以避免不必要的字符串比较。

方法二：DP + Trie

构建字典树存储所有单词，然后在DP过程中使用Trie进行高效匹配。

方法三：DP + AC自动机

对于更复杂的匹配需求，可以使用AC自动机，但对于这个问题可能过于复杂。

本题的核心思路是：

  1. 定义 dp[i] 为构造前 i 个字符的最小代价
  2. 对于每个位置 i，尝试所有可能的单词匹配
  3. 如果 words[j] 能匹配 target[i-len...i-1]，则更新 dp[i] = min(dp[i], dp[i-len] + costs[j])
  4. 使用哈希表优化匹配过程，避免超时

时间复杂度主要取决于单词总长度和target长度的乘积。

代码实现

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        int n = target.length();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        // 将单词按长度分组，并记录最小代价
        unordered_map<string, int> wordCost;
        for (int i = 0; i < words.size(); i++) {
            if (wordCost.find(words[i]) == wordCost.end() || wordCost[words[i]] > costs[i]) {
                wordCost[words[i]] = costs[i];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (auto& [word, cost] : wordCost) {
                int len = word.length();
                if (len <= i && dp[i - len] != INT_MAX) {
                    if (target.substr(i - len, len) == word) {
                        dp[i] = min(dp[i], dp[i - len] + cost);
                    }
                }
            }
        }
        
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        n = len(target)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        # 将单词和最小代价映射
        word_cost = {}
        for word, cost in zip(words, costs):
            if word not in word_cost or word_cost[word] > cost:
                word_cost[word] = cost
        
        for i in range(1, n + 1):
            for word, cost in word_cost.items():
                word_len = len(word)
                if word_len <= i and dp[i - word_len] != float('inf'):
                    if target[i - word_len:i] == word:
                        dp[i] = min(dp[i], dp[i - word_len] + cost)
        
        return dp[n] if dp[n] != float('inf') else -1

public class Solution {
    public int MinimumCost(string target, string[] words, int[] costs) {
        int n = target.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        // 将单词和最小代价映射
        Dictionary<string, int> wordCost = new Dictionary<string, int>();
        for (int i = 0; i < words.Length; i++) {
            if (!wordCost.ContainsKey(words[i]) || wordCost[words[i]] > costs[i]) {
                wordCost[words[i]] = costs[i];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            foreach (var kvp in wordCost) {
                string word = kvp.Key;
                int cost = kvp.Value;
                int wordLen = word.Length;
                
                if (wordLen <= i && dp[i - wordLen] != int.MaxValue) {
                    if (i >= wordLen && target.Substring(i - wordLen, wordLen) == word) {
                        dp[i] = Math.Min(dp[i], dp[i - wordLen] + cost);
                    }
                }
            }
        }
        
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }
}

var minimumCost = function(target, words, costs) {
    const n = target.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    const wordMap = new Map();
    for (let i = 0; i < words.length; i++) {
        if (!wordMap.has(words[i])) {
            wordMap.set(words[i], costs[i]);
        } else {
            wordMap.set(words[i], Math.min(wordMap.get(words[i]), costs[i]));
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (dp[i] === Infinity) continue;
        
        for (const [word, cost] of wordMap) {
            if (i + word.length <= n && target.substring(i, i + word.length) === word) {
                dp[i + word.length] = Math.min(dp[i + word.length], dp[i] + cost);
            }
        }
    }
    
    return dp[n] === Infinity ? -1 : dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × m × L)
空间复杂度O(n + W)

其中：

  • n 是 target 的长度
  • m 是去重后的单词数量
  • L 是平均单词长度
  • W 是所有单词的总空间

相关题目