class Solution {
public:
int Leetcode(vector<string>& words) {
}
};
LCP 69. Hello LeetCode!
力扣嘉年华同样准备了纪念品展位，参观者只需要集齐 helloleetcode 的 13 张字母卡片即可获得力扣纪念章。
在展位上有一些由字母卡片拼成的单词，words[i][j] 表示第 i 个单词的第 j 个字母。
你可以从这些单词中取出一些卡片，但每次拿取卡片都需要消耗游戏代币，规则如下：
从一个单词中取一个字母所需要的代币数量，为该字母左边和右边字母数量之积
可以从一个单词中多次取字母，每个字母仅可被取一次
例如：从
example中取出字母a，需要消耗代币2*4=8，字母取出后单词变为exmple； 再从中取出字母m，需要消耗代币2*3=6，字母取出后单词变为exple；
请返回取得 helloleetcode 这些字母需要消耗代币的 最少 数量。如果无法取得，返回 -1。
注意：
helloleetcode 示例 1：
输入：
words = ["hold","engineer","cost","level"]输出：
5解释：最优方法为： 从
hold依次取出h、o、l、d， 代价均为0从engineer依次取出第1个e与最后一个e， 代价为0和5*1=5从cost取出c、o、t， 代价均为0从level依次取出l、l、e、e， 代价均为0所有字母恰好可以拼成helloleetcode，因此最小的代价为5
示例 2：
输入：
words = ["hello","leetcode"]输出：
0
提示：
n == words.lengthm == words[i].length1 <= n <= 241 <= m <= 8words[i][j] 仅为小写字母原站题解
java 解法, 执行用时: 348 ms, 内存消耗: 42.7 MB, 提交时间: 2023-09-04 10:16:58
class Solution {
Map<Character, int[]> hmap;
int[][] dp;
int len;
List<Map<Integer, Integer>> costs;
public int Leetcode(String[] words) {
len = words.length;
hmap = new HashMap<>(); //字符-位置，数量，位掩码
hmap.put('c', new int[]{10, 1, 1});
hmap.put('d', new int[]{9, 1, 1});
hmap.put('e', new int[]{0, 4, 7});
hmap.put('h', new int[]{8, 1, 1});
hmap.put('l', new int[]{3, 3, 3});
hmap.put('o', new int[]{5, 2, 3});
hmap.put('t', new int[]{7, 1, 1});
//求每个单词的mask和cost
costs = new ArrayList<>();
for(String word : words){
Map<Integer, Integer> hp = new HashMap<>();
dfs(hp, word, 0, 0);
costs.add(hp);
}
dp = new int[len][1<<11];
for(int i = 0; i < len; i++) Arrays.fill(dp[i], -1);
int ans = dfs2(0, 0);
return ans == 0x3f3f3f3f ? -1 : ans;
// return 0;
}
void dfs(Map<Integer, Integer> hp, String str, int mask, int tot){
if(!hp.containsKey(mask) || hp.get(mask) > tot) hp.put(mask, tot);
if("".equals(str)) return;
int n = str.length();
for(int i = 0; i < n; i++){
if(!hmap.containsKey(str.charAt(i))) continue;
int[] pnm = hmap.get(str.charAt(i));
int cnt = (mask >> pnm[0]) & pnm[2];
if(cnt < pnm[1]){ //可以添加字母
dfs(hp, str.substring(0, i)+str.substring(i+1, n), mask+(1<<pnm[0]), tot+i*(n-i-1));
}
}
}
int merge(int mask, int add){
for(int[] pnm : hmap.values()){
int c1 = (mask>>pnm[0]) & pnm[2];
int c2 = (add>>pnm[0]) & pnm[2];
if(c1 + c2 > pnm[1]) return -1;
mask += c2<<pnm[0];
}
return mask;
}
//记忆化搜索 dp[wi][mask]表示 从第wi个字符串开始，当前状态为mask时还需要付出的最小代价
int dfs2(int wi, int mask){
if(wi == len) return mask == 2012 ? 0 : 0x3f3f3f3f;
if(dp[wi][mask] != -1) return dp[wi][mask];
int res = 0x3f3f3f3f;
Map<Integer, Integer> hp = costs.get(wi);
for(Map.Entry<Integer, Integer> e : hp.entrySet()){
int m = merge(mask, e.getKey());
if(m >= 0){
res = Math.min(res, dfs2(wi+1, m)+e.getValue());
}
}
dp[wi][mask] = res;
return res;
}
}
golang 解法, 执行用时: 400 ms, 内存消耗: 7 MB, 提交时间: 2023-09-04 10:16:39
const keys = "elohtcd"
const full = 2012 // 0b11111011100，每个字母都选到了对应的上限
// pos：字母在二进制上的起始位置
// limit：这个字母能选择的上限
// mask：位掩码
var rules = ['z' + 1]struct{ pos, limit, mask int }{
'e': {0, 4, 7},
'l': {3, 3, 3},
'o': {5, 2, 3},
'h': {7, 1, 1},
't': {8, 1, 1},
'c': {9, 1, 1},
'd': {10, 1, 1},
}
// 合并两种选择字母的方案
func merge(cur, add int) int {
for _, c := range keys {
r := rules[c]
c1 := cur >> r.pos & r.mask
c2 := add >> r.pos & r.mask
if c1+c2 > r.limit {
return -1
}
cur += c2 << r.pos
}
return cur
}
func Leetcode(words []string) int {
const inf = math.MaxInt32 / 2
n := len(words)
// 预处理每个单词的每种选择字母的方案所消耗的代币的最小值
costs := make([][1 << 11]int, n)
for i, word := range words {
for j := range costs[i] {
costs[i][j] = inf
}
var f func(string, int, int)
f = func(s string, mask, tot int) {
costs[i][mask] = min(costs[i][mask], tot)
for j, c := range s { // 枚举选择字母的位置
r := rules[c]
if mask>>r.pos&r.mask < r.limit { // 可以选字母 c
f(s[:j]+s[j+1:], mask+1<<r.pos, tot+j*(len(s)-1-j))
}
}
}
f(word, 0, 0)
}
dp := make([][1 << 11]int, n)
for i := range dp {
for j := range dp[i] {
dp[i][j] = -1
}
}
var f func(int, int) int
f = func(i, mask int) int {
if i == n {
if mask == full {
return 0
}
return inf // inf 表示不合法，没有选完要求的字母
}
ptr := &dp[i][mask]
if *ptr != -1 {
return *ptr
}
res := inf
for add, tot := range costs[i][:] {
if tot >= res { // 剪枝
continue
}
m2 := merge(mask, add)
if m2 >= 0 {
res = min(res, f(i+1, m2)+tot)
}
}
*ptr = res
return res
}
ans := f(0, 0)
if ans == inf {
return -1
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
python3 解法, 执行用时: 3160 ms, 内存消耗: 46.6 MB, 提交时间: 2023-09-04 10:16:01
'''
预处理 + 状态压缩dp
1. 用位运算表示字母选择情况，由于一个字母可以选多个，
因此要对二进制「分区」，每个区域表示对应字母的个数。
2. 写一个记忆化搜索，f(i,mask) 表示从第 i 个单词开始选，已经选择的单词为 mask 时，
后续消耗代币的最小值。枚举 words[i] 的所有合法选择方案转移到 f(i+1,mask′)。
3. 因此需要预处理每个 words[i] 的每种选择字母的方案所消耗的代币的最小值，
由于字符串很短，直接写个爆搜即可。
'''
# (字母在二进制上的起始位置, 这个字母能选择的上限, 位掩码)
RULES = {
'e': (0, 4, 7),
'l': (3, 3, 3),
'o': (5, 2, 3),
'h': (7, 1, 1),
't': (8, 1, 1),
'c': (9, 1, 1),
'd': (10, 1, 1),
}
FULL = 2012 # 0b11111011100，每个字母都选到了对应的上限
# 合并两种选择字母的方案
def merge(cur: int, add: int) -> int:
for pos, limit, m in RULES.values():
c1 = (cur >> pos) & m
c2 = (add >> pos) & m
if c1 + c2 > limit: return -1
cur += c2 << pos
return cur
class Solution:
def Leetcode(self, words: List[str]) -> int:
# 预处理每个单词的每种选择字母的方案所消耗的代币的最小值
costs = []
for word in words:
cost = {}
def dfs(s: str, mask: int, tot: int) -> None:
if mask not in cost or tot < cost[mask]:
cost[mask] = tot
for i, c in enumerate(s): # 枚举选择字母的位置
if c not in RULES: continue
pos, limit, m = RULES[c]
if (mask >> pos) & m < limit: # 可以选字母 c
dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))
dfs(word, 0, 0)
costs.append(cost)
@cache
def dfs(i: int, mask: int) -> int:
if i == len(words):
return 0 if mask == FULL else inf # inf 表示不合法，没有选完要求的字母
res = inf
for add, tot in costs[i].items():
if tot >= res: continue # 剪枝
m = merge(mask, add)
if m >= 0:
res = min(res, tot + dfs(i + 1, m))
return res
ans = dfs(0, 0)
return ans if ans < inf else -1