JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-09-25
目录

贴纸拼词Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能,则返回 -1 。

注意:在所有的测试用例中,所有的单词都是从 1000 个最常见的美国英语单词中随机选择的,并且 target 被选择为两个随机单词的连接。

示例 1:

输入: stickers = ["with","example","science"], target = "thehat"
输出:3
解释:
我们可以使用 2 个 "with" 贴纸,和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后,就可以形成目标 “thehat“ 了。
此外,这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入:stickers = ["notice","possible"], target = "basicbasic"
输出:-1
解释:我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

  • n == stickers.length
  • 1 <= n <= 50
  • 1 <= stickers[i].length <= 10
  • 1 <= target.length <= 15
  • stickers[i] 和 target 由小写英文单词组成

# 思路

无脑枚举+记忆化剪枝

# 解法


class Solution {

    // 无脑枚举+记忆化剪枝
public int minStickers(String[] stickers, String target) {
        int l = target.length();
        long full = (1<<l)-1;
        Map<Long,Integer> memory = new HashMap<>();
        memory.put(full,0);
        return count(stickers,target,0,memory);
    }

    public long contribute(String target, long state, String sticker){
        int[] val = new int[26];
        for(int i = 0 ; i < sticker.length() ; i++){
            val[sticker.charAt(i)-'a']++;
        }
        int n = target.length();
        for(int i = 0 ; i < n ; i++){
            if(((state>>i)&1) == 0){
                if(val[target.charAt(n-i-1)-'a'] > 0){
                    state += (1<<i);
                    val[target.charAt(n-i-1)-'a']--;
                }
            }
        }
        return state;
    }

    public int count(String[] stickers, String target, long state, Map<Long,Integer> memory){
        if(memory.containsKey(state)){
            return memory.get(state);
        }
        long temp;
        int val = Integer.MAX_VALUE;
        int n = stickers.length;
        int amount;
        for(int i = 0 ; i < n ; i++){
            temp = contribute(target,state,stickers[i]);
            if(temp != state){
                amount = count(stickers,target,temp,memory);
                if(amount != -1){
                    val = Math.min(val,1+amount);
                }
            }
        }
        if(val == Integer.MAX_VALUE){
            memory.put(state,-1);
            return -1;
        }
        memory.put(state,val);
        return val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式