[Swift]LeetCode819.最常见的单词|MostCommonWord

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

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

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

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

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

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

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn't banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:

Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.
1 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中，而且答案唯一。

禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

示例：

输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释: 
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。 
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"）， 
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。

说明：

1 <= 段落长度 <= 1000.
1 <= 禁用单词个数 <= 100.
1 <= 禁用单词长度 <= 10.
答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
paragraph 只包含字母、空格和下列标点符号!?',;.
不存在没有连字符或者带有连字符的单词。
单词里只包含字母，不会出现省略号或者其他标点符号。

24ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3       let paraArray = paragraph.split { (c) -> Bool in
 4             let ascii = c.unicodeScalars.first!.value
 5             return ascii < 65 || (ascii > 90 && ascii < 97) || ascii > 122
 6         }
 7         
 8         let banned: Set<String> = Set(banned)
 9         
10         var map: [String: Int] = [:]
11         for word in paraArray {
12             map[String(word).lowercased(), default: 0] += 1
13         }
14         
15         for (key, _) in map.sorted(by: { (word1, word2) -> Bool in
16             return word1.value > word2.value
17         }) {
18             if !banned.contains(key) {
19                 return key
20             }
21         }
22         
23         return ""
24     }
25 }

36ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var paragraph = Array(paragraph.lowercased())
 4         for i in 0..<paragraph.count {
 5             if paragraph[i] < "a" || paragraph[i] > "z" {
 6                 paragraph[i] = " "
 7             }
 8         }
 9         let words = String(paragraph).split(separator: " ").map{String($0)}
10         var result = ""
11         var max = 0
12         var map = [String:Int]()
13         for word in words {
14             if !banned.contains(word) {
15                 map[word] = (map[word] ?? 0) + 1
16                 if map[word]! > max {
17                     max = map[word]!
18                     result = word
19                 }
20             }
21         }
22         return result
23     }
24 }

44ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var paras = Array(paragraph.lowercased())
 4         for i in paras.indices {
 5             if paras[i] < "a" || paras[i] > "z" { paras[i] = " " }
 6         }
 7         let words = String(paras).components(separatedBy: " ")
 8         var res = ""
 9         var mx = 0
10         var m = [String: Int]()
11         for word in words where !word.isEmpty {
12             if !banned.contains(word) {
13                 m[word, default: 0] += 1
14                 if m[word]! > mx {
15                     mx = m[word]!
16                     res = word
17                 }
18             }
19         }
20         return res
21     }
22 }

48ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var counts: [String: Int] = [:]
 4         
 5         // let s = Set(banned)
 6         
 7         for w in paragraph.lowercased().components(separatedBy: .punctuationCharacters).joined(separator: " ").split(separator: " ") {
 8 
 9             counts[String(w), default: 0] += 1
10             // if counts[String(w)] != nil {
11             //     counts[String(w)]! += 1
12             // } else {
13             //     counts[String(w)] = 1
14             // }
15         }
16         
17         // let k = counts.filter({ !s.contains($0.key) }).max(by: { $1.value > $0.value })!.key
18         
19         return counts.lazy.filter({ !Set(banned).contains($0.key) }).max(by: { $1.value > $0.value })!.key
20         // return counts.max(by: { $1.value > $0.value })!.key    
21     }
22 }

52ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var wordCount = [String: Int]()
 4         var bannedWords = Set(banned)
 5         for substring in paragraph.replacingOccurrences(of: ",", with: " ").split(separator: " ") {
 6             let word = substring.lowercased().trimmingCharacters(in: .punctuationCharacters)
 7             if !bannedWords.contains(word) {
 8                 wordCount[word] = wordCount[word, default: 0] + 1
 9             }
10         }
11         return wordCount.max { a, b in a.value < b.value}!.key
12     }
13 }

60ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var bannedDict = Set<String>()
 4         banned.forEach{bannedDict.insert($0.lowercased())}
 5         var paraComponents = paragraph.lowercased().components(separatedBy: .punctuationCharacters).joined(separator: " ").components(separatedBy: " ").filter{$0 != ""}
 6         var memo = [String : Int]()
 7         var count = 0
 8         var answer = ""
 9         
10         for comp in paraComponents{
11             if bannedDict.contains(comp){
12                 continue
13             }
14             if memo[comp] != nil{
15                 memo[comp] = memo[comp]! + 1
16             }else{
17                 memo[comp] = 1
18             }
19             
20             if memo[comp]! > count {
21                 count = memo[comp]!
22                 answer = comp
23             }
24         }
25         
26         return answer
27     }
28 }

Runtime: 60 ms

Memory Usage: 21 MB

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         
 4         let bannedSet = Set(banned)
 5         
 6         let wordArray = paragraph
 7             .lowercased()
 8             .components(separatedBy: CharacterSet(["!", "?", "'", ",", ";", ".", " "]))
 9             .filter { !$0.isEmpty && !bannedSet.contains($0) }
10         
11         var wordFrequencyDict: [String : UInt] = [:]
12         
13         for word in wordArray {
14             wordFrequencyDict[word] = wordFrequencyDict[word, default: 0] + 1
15         }
16         
17         return wordFrequencyDict.max { $0.value < $1.value }!.key
18     }
19 }

64ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String,
 3                         _ banned: [String]) -> String {
 4         // lower case
 5         let paragraph = paragraph.lowercased()
 6         let banned = Set(banned)
 7         // store the words
 8         var onHold: String? = nil
 9         var storage: [String: Int] = [:]
10         for char in paragraph {
11             if char.unicodeScalars.allSatisfy(CharacterSet.alphanumerics.contains(_:)) {
12                 if onHold == nil {
13                     onHold = ""
14                 }
15                 onHold!.append(char)
16             } else {
17                 guard onHold != nil else { continue }
18                 storage[onHold!, default: 0] += 1
19                 onHold = nil
20             }
21         }
22         if !(onHold?.isEmpty ?? true) {
23             storage[onHold!, default: 0] += 1
24         }
25         // find the max
26         var max = -1
27         var maxKey = ""
28         for (key, value) in storage {
29             if value > max && !banned.contains(key) {
30                 maxKey = key
31                 max = value
32             }
33         }
34         return maxKey
35     }
36 }

68ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         guard paragraph.count > 0 else {
 4             return paragraph
 5         }
 6         let arr = paragraph.components(separatedBy: CharacterSet.punctuationCharacters).joined(separator:" ").components(separatedBy: .whitespaces).filter({!$0.isEmpty})
 7         var map = [String:Int]()
 8         var max = Int.min
 9         var res = ""
10         for string in arr {
11             var st = string.lowercased()
12             if banned.contains(st) {continue}
13             if let count = map[st] {
14                 map[st] = count + 1
15             }
16             else{
17                 map[st] = 1
18             }
19             if map[st]! > max {
20                 max = map[st]!
21                 res = st
22             }
23         }
24         return res
25     }
26 }

72ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var lower = paragraph.lowercased()
 4         var para = splitString(lower)
 5         var dict = getWordCountDict(para, banned: banned)
 6         var maxCount = 0
 7         var result = ""
 8         for (s, c) in dict {
 9             if c > maxCount {
10                 maxCount = c
11                 result = s
12             }
13         }
14         return result
15     }
16     
17     func splitString(_ s: String) -> [String] {
18         return s.components(separatedBy:CharacterSet(charactersIn:",. !?;:'"))
19     }
20     
21     func getWordCountDict(_ array: [String], banned: [String]) -> [String: Int] {
22         var result = [String: Int]()
23         for w in array {
24             if w.length == 0 {
25                 continue
26             }
27             if banned.contains(w) {
28                 continue
29             }
30             if let v = result[w] {
31                 let nv = v + 1
32                 result[w] = nv
33             } else {
34                 result[w] = 1
35             }
36         }
37         return result
38     }    
39 }

84ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         var counts: [String: Int] = [:]
 4         
 5         for w in  paragraph.components(separatedBy: .punctuationCharacters).joined(separator: " ").lowercased().split(separator: " ") where !Set(banned).contains(String(w)) {
 6             let sw = String(w)
 7             
 8             if counts[sw] != nil {
 9                 counts[sw]! += 1
10             } else {
11                 counts[sw] = 1
12             }
13         }
14         
15         return counts.max(by: { $1.value > $0.value })!.key    
16     }
17 }

92ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {        
 3         let formattedPara = formattedParagraph(paragraph)
 4         var bannedWords = Set<String>()
 5         print(formattedPara)
 6         //throw them into a set
 7         for word in  banned {
 8             bannedWords.insert(word)
 9         }
10         var map = [String: Int]()
11         //now go through each word and if it's not in bannedWords, push to a dict
12         //with it's count
13         for word in formattedPara.components(separatedBy: " ") {
14             if !bannedWords.contains(word) && !word.isEmpty {
15                 map[word, default: 0] += 1
16             }
17         }        
18         //now sort the dict values in decreasing order        
19         var sortedTupleArr = map.sorted {$0.1 > $1.1}
20         return sortedTupleArr[0].0        
21     }
22     
23     private func formattedParagraph( _ para: String) -> String {
24         var para = para.lowercased()
25         let pattern = "[^A-Za-z]"
26         let regex = try! NSRegularExpression(pattern: pattern)
27         let range = NSRange(location: 0, length: para.count)
28         let para1 = regex.stringByReplacingMatches(in: para, options: .reportProgress,
29                             range: range, withTemplate: " ")
30         //print(para1)
31         return para1
32     }
33 }

96ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         
 4         let lowercaseParagraph = paragraph.lowercased()
 5         let components = lowercaseParagraph.components(separatedBy: CharacterSet.letters.inverted).filter({ $0 != "" })
 6         let set = NSCountedSet(array:components)
 7         let bannedSet = Set(banned)
 8         
 9         var max = 0   
10         var answer = ""
11                                                                                                            
12         for word in set{
13             if let answerWord = word as? String{
14                 let repeatCount = set.count(for:answerWord)
15                 
16                 if ( repeatCount > max && !bannedSet.contains(answerWord)){
17                     max = repeatCount
18                     answer = answerWord
19                 }
20             }
21         }
22                                                                                                            
23        return answer
24     }
25 }

100ms

 1 class Solution {
 2     func mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
 3         let letters : Set<Character> =  Set("abcdefghijklmnopqrstuvwxyz")
 4         let w = paragraph.replacingOccurrences(of: "[!?',;.]", with: " ", options: .regularExpression, range: nil)
 5         var banned = Set(banned)
 6         let words = w.components(separatedBy: " ").filter { $0.count > 0 }.map { $0.lowercased().filter { letters.contains($0) } }.filter { !banned.contains($0) }
 7         var count: [String: Int] = [:]
 8         var maxC = 1
 9         var res = words[0]
10         for word in words {
11             if let some = count[word] {
12                 count[word] = some + 1
13                 if (some + 1) > maxC {
14                     maxC = some + 1
15                     res = word
16                 }
17             } else {
18                 count[word] = 1
19             }
20         }
21         return res
22     }
23 }