[Swift]LeetCode1160.拼写单词|FindWordsThatCanBeFormedbyCharacters

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

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

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

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

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

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

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的长度之和。

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

216ms

 1 class Solution {
 2   func countCharacters(_ words: [String], _ chars: String) -> Int {
 3     var res = 0
 4     var charMap = [Character: Int]()
 5     for char in chars {
 6       charMap[char] = charMap[char, default: 0] + 1
 7     }
 8     for word in words {
 9       var shouldAdd = true
10       var charMapCopy = charMap
11       for char in word {
12         if let val = charMapCopy[char] {
13           if val > 0 {
14             charMapCopy[char] = val - 1
15           } else {
16             shouldAdd = false
17             break
18           }
19         } else {
20           shouldAdd = false
21           break
22         }
23       }
24       if shouldAdd {
25         res += word.count
26       }
27     }
28     return res
29   }
30 }

244ms

 1 class Solution {
 2     typealias Counter = [Character:Int]
 3     var charsCounter: Counter = Counter()
 4     var charsCount = 0
 5     func countCharacters(_ words: [String], _ chars: String) -> Int {
 6         var ans = 0
 7         charsCounter = getWordCounter(chars)
 8         charsCount = chars.count
 9         for word in words {
10             if valid(word) {
11                 print(word)
12                 ans += word.count
13             }
14         }
15         return ans
16     }
17     
18     private func getWordCounter(_ word: String) -> Counter {
19         var ans = Counter()
20         for ch in word {
21             if ans[ch] == nil {
22                 ans[ch] = 1
23             } else {
24                 ans[ch] = ans[ch]! + 1
25             }
26         }
27         return ans
28     }
29     private func valid(_ word: String) -> Bool {
30         if word.count > charsCount {
31             return false
32         }
33         var tempCharsCounter  =  charsCounter
34         for key in word {
35             if  tempCharsCounter[key]  == nil {
36                 return  false
37             }
38             tempCharsCounter[key] = tempCharsCounter[key]!  - 1
39             if tempCharsCounter[key] == 0 {
40                 tempCharsCounter.removeValue(forKey: key)
41             }
42         }
43         return true
44     }
45 }

288ms

 1 class Solution {
 2     func countCharacters(_ words: [String], _ chars: String) -> Int {
 3         
 4         if words.count == 0 { return 0 }
 5         if chars.count == 0 { return 0 }
 6         
 7         var charDict = [Character: Int]()
 8         var charStr = Array(chars)
 9         
10         for ch in charStr {
11             charDict[ch, default: 0] += 1
12         }
13         
14         var result = 0
15         for word in words {
16             let wordChars = Array(word)
17             var wordDict = charDict
18             var canForm = true
19             
20             for wch in wordChars {
21                guard var charFreq = wordDict[wch] else {
22                    canForm = false
23                    break 
24                }
25                 charFreq -= 1
26                 
27                 if charFreq < 0 {
28                     canForm = false
29                     break
30                 }
31                 
32                 wordDict[wch] = charFreq
33             }
34             
35             if canForm {
36                 result += word.count
37             }
38         }
39         
40         return result
41     }
42 }

292ms

 1 class Solution {
 2     func countCharacters(_ words: [String], _ chars: String) -> Int {
 3                 
 4         let chars1 = Array(chars)
 5         var dic = [Character: Int]()
 6         for c in chars1 {
 7             dic[c, default: 0] += 1
 8         }
 9 
10         var ans = 0
11         for word in words {
12             var tmpDic = dic
13             let chs = Array(word)
14             ans += chs.count
15             for c in chs {
16                 if tmpDic[c ,default: 0] <= 0 {
17                     ans -= chs.count
18                     break
19                 }
20                 tmpDic[c ,default: 0] -= 1
21             }
22         }
23         return ans
24     }
25 }

520ms

 1 class Solution {
 2     func countCharacters(_ words: [String], _ chars: String) -> Int {
 3         
 4         var count = 0
 5         
 6         let mappedChars = chars.reduce(into: [:]) {
 7 
 8             counts, character in
 9             counts[character, default: 0] += 1
10             
11         }
12         
13         for word in words {
14             
15             if isInChars(word, chars: mappedChars) {
16                 count += word.count
17             }
18             
19         }
20         
21         return count
22     }
23     
24     func isInChars(_ word: String, chars: [String.Element: Int]) -> Bool {
25         
26         let mappedWord = word.reduce(into: [:]) {
27             counts, character in
28             counts[character, default: 0] += 1
29         }
30         
31         for each in mappedWord {
32             
33             if !chars.keys.contains(each.key) {
34                 return false
35             }
36             
37             if each.value > chars[each.key]! {
38                 return false
39             }
40             
41         }
42         
43         return true
44     }
45 }

Runtime: 920 ms

Memory Usage: 21 MB

 1 class Solution {
 2     func countCharacters(_ words: [String], _ chars: String) -> Int {
 3         var A:[Int:Int] = [Int:Int]()
 4         let arrChars:[Int] = Array(chars).map{$0.ascii}
 5         for c in arrChars
 6         {
 7             A[c - 97,default:0] += 1          
 8         }
 9         var ret:Int = 0
10         for s in words
11         {
12             var cnt:[Int:Int] = [Int:Int]()
13             let arrS:[Int] = Array(s).map{$0.ascii}
14             for c in arrS
15             {
16                 cnt[c - 97,default:0] += 1   
17             }
18             var found:Bool = false
19             for k in 0..<26
20             {
21                 if cnt[k,default:0] > A[k,default:0]
22                 {
23                     found = true
24                 }
25             }
26             if !found
27             {
28                 ret += s.count
29             }
30         }
31         return ret        
32     }
33 }
34 
35 //Character扩展 
36 extension Character  
37 {  
38   //Character转ASCII整数值(定义小写为整数值)
39    var ascii: Int {
40        get {
41            return Int(self.unicodeScalars.first?.value ?? 0)
42        }       
43     }
44 }