Hello LeetCode!
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 1128 ms, 内存: 22.0 MB
/*
* Problem Statement:
* Given a list of words, determine the minimum cost to collect all the letters in the string "helloleetcode" from these words.
* The cost of taking a letter from a word is calculated as the product of the number of letters to its left and right in the word.
* If it's not possible to collect all the letters, return -1.
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int minCostToCollectLetters(String[] words) {
String target = "helloleetcode";
Map<Character, Integer> targetCount = target.chars()
.mapToObj(c -> (char)c)
.collect(Collectors.toMap(c -> c, c -> 1, Integer::sum));
Map<Character, List<Integer>> costs = new HashMap<>();
Arrays.stream(words).forEach(word -> {
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (targetCount.containsKey(c)) {
int cost = i * (word.length() - i - 1);
costs.computeIfAbsent(c, k -> new ArrayList<>()).add(cost);
}
}
});
int totalCost = 0;
for (Map.Entry<Character, Integer> entry : targetCount.entrySet()) {
char c = entry.getKey();
int required = entry.getValue();
if (costs.containsKey(c)) {
List<Integer> availableCosts = costs.get(c);
if (availableCosts.size() < required) return -1;
Collections.sort(availableCosts);
totalCost += availableCosts.subList(0, required).stream().mapToInt(Integer::intValue).sum();
} else {
return -1;
}
}
return totalCost;
}
}
解释
方法:
此题解采用了动态规划和状态压缩的策略。首先,创建一个数组 'value' 来存储从给定单词中取出特定字母序列的最小代价。该数组通过动态规划更新,考虑所有可能的字母组合和相应的消耗。对于每个单词,'value' 数组考虑所有子序列(使用位掩码表示)并计算从这些子序列中获取特定字母的代价。接着,对于目标字符串 'helloleetcode',构造一个转移矩阵 'next_st',该矩阵记录了在当前状态下添加一个新字符后可能达到的新状态。在主函数 'Leetcode' 中,使用一个字典 'dp' 来动态记录从每个单词中取出特定字母序列以拼成目标字符串的最小总代价。遍历每个单词,并递归地考虑取或不取当前字符的情况,通过比较不同选择的代价来更新 'dp'。最终,'dp' 中的最小值就是答案。
时间复杂度:
O((m * 2^m) + (k * 2^k) + (n * m^2 * 2^k))
空间复杂度:
O(m * 2^m + k * 2^k + 2^k)
代码细节讲解
🦆
在动态规划数组`value`的计算中,为什么要使用位掩码来表示字母的选择?这样做有什么优势?
▷🦆
如何理解并计算字母取出后的代价,特别是`value[ln][mask]`中的`left * right`这一部分是如何得出的?
▷🦆
在`next_st`数组中,每个状态如何转移到新状态,具体的转移逻辑是怎样的?
▷