leetcode
leetcode 3001 ~ 3050
Hello LeetCode!

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`的计算中,为什么要使用位掩码来表示字母的选择?这样做有什么优势?
在动态规划中使用位掩码来表示字母的选择,主要是因为位掩码允许我们以非常紧凑和高效的方式来表示和操作字母组合的状态。每个位(bit)可以代表一个字母是否被选择(1表示选中,0表示未选中),这样就可以使用整数的位运算(如位与、位或和位非)来快速处理状态的转移。这种方法的优势在于:1) 存储效率高,一个整数可以表示多个字母的选择状态;2) 计算效率高,位运算通常比其他类型的数据操作更快;3) 易于实现状态转移,可以直接通过位操作实现状态的添加和检查。
🦆
如何理解并计算字母取出后的代价,特别是`value[ln][mask]`中的`left * right`这一部分是如何得出的?
在计算`value[ln][mask]`时,每个位掩码`mask`代表了从单词中选择字母的不同组合,而`left * right`代表的是选择当前字母的代价。这里,`left`和`right`分别表示当前字母左侧和右侧未被选择的字母数量。当选择一个字母时,左侧未选择的字母数量和右侧未选择的字母数量的乘积可以被视作这次选择的'代价',因为它反映了这个字母在单词中的'位置重要性'。具体来说,如果一个字母被选择,那么它左侧和右侧的未选择字母越多,意味着它在原单词中的位置越靠中间,其选择可能导致的组合变化和影响更大,因此代价也就更高。
🦆
在`next_st`数组中,每个状态如何转移到新状态,具体的转移逻辑是怎样的?
在`next_st`数组的计算中,每个状态代表了目标字符串`helloleetcode`中已经被选择的字母集合。数组的索引使用位掩码表示,每个位对应目标字符串中的一个字符,如果该位为1,则表示相应位置的字符已被选择。转移逻辑是:对于每个当前状态(位掩码),遍历目标字符串中的每个字符。如果当前字符在状态中未被选择(对应位为0),则通过位或运算将该字符的位设为1,从而生成一个新状态。这个新状态表示在当前选择的基础上,又选择了一个新的字符。这样,`next_st`数组通过记录每个状态可以转移到的所有可能的新状态,使得我们可以在动态规划中,根据当前已选择的字符集合,直接查找到添加任一新字符后的新状态。

相关问题