[Swift]LeetCode691.贴纸拼词|StickerstoSpellWord

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10501868.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

We are given N different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given targetstring by cutting individual letters from your collection of stickers and rearranging them.

You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

Example 1:

Input:

["with", "example", "science"], "thehat"

Output:

Explanation:

We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input:

["notice", "possible"], "basicbasic"

Output:

-1

Explanation:

We can't form the target "basicbasic" from cutting letters from the given stickers.

Note:

stickers has length in the range [1, 50].
stickers consists of lowercase English words (without apostrophes).
target has length in the range [1, 15], and consists of lowercase English letters.
In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words.
The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。

如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。

拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

示例 1：

输入：

["with", "example", "science"], "thehat"

输出：

解释：

我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2：

输入：

["notice", "possible"], "basicbasic"

输出：

-1

解释：

我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示：

stickers 长度范围是 [1, 50]。
stickers 由小写英文单词组成（不带撇号）。
target 的长度在 [1, 15] 范围内，由小写字母组成。
在所有的测试案例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。
时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

Runtime: 136 ms

Memory Usage: 20 MB

 1 class Solution {
 2     func minStickers(_ stickers: [String], _ target: String) -> Int {
 3         var N:Int = stickers.count
 4         var freq:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:26),count:N)
 5         var memo:[String:Int] = [String:Int]()
 6         memo[""] = 0
 7         for i in 0..<N
 8         {
 9             for char in stickers[i].characters
10             {
11                 freq[i][char.ascii - 97] += 1
12             }
13         }
14         return helper(&freq, target, &memo)
15     }
16         
17     func helper(_ freq:inout [[Int]], _ target: String,_ memo:inout [String:Int]) -> Int
18     {
19         if let num:Int = memo[target]
20         {
21             return num
22         }       
23         var res:Int = Int.max
24         var N:Int = freq.count
25         var cnt:[Int] = [Int](repeating:0,count:26)
26         for char in target.characters
27         {
28             cnt[char.ascii - 97] += 1
29         }
30         for i in 0..<N
31         {
32             if freq[i][target[0].ascii - 97] == 0
33             {
34                 continue
35             }
36             var t:String = String()
37             for j in 0..<26
38             {
39                 if cnt[j] - freq[i][j] > 0
40                 {
41                     for i in 0..<(cnt[j] - freq[i][j])
42                     {
43                         t.append((97 + j).ASCII)
44                     }
45                     
46                 }
47             }
48             var ans:Int = helper(&freq, t, &memo)
49             if ans != -1 {res = min(res, ans + 1)}
50         }
51         memo[target,default:0] = (res == Int.max) ? -1 : res
52         return memo[target,default:0]
53     }
54 }
55     
56 //String扩展
57 extension String {        
58     //subscript函数可以检索数组中的值
59     //直接按照索引方式截取指定索引的字符
60     subscript (_ i: Int) -> Character {
61         //读取字符
62         get {return self[index(startIndex, offsetBy: i)]}
63     }
64 }
65 
66 //Character扩展 
67 extension Character  
68 {  
69   //Character转ASCII整数值(定义小写为整数值)
70    var ascii: Int {
71        get {
72            return Int(self.unicodeScalars.first?.value ?? 0)
73        }       
74     }    
75 }
76 
77 //Int扩展
78 extension Int
79 {
80     //Int转Character,ASCII值(定义大写为字符值)
81     var ASCII:Character 
82     {
83         get {return Character(UnicodeScalar(self)!)}
84     }
85 }