[Swift]LeetCode820.单词的压缩编码|ShortEncodingofWords

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

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

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

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

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

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

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母。

Runtime: 216 ms

Memory Usage: 20 MB

 1 class Solution {
 2     func minimumLengthEncoding(_ words: [String]) -> Int {
 3         var res:Int = 0
 4         var st:Set<String> = Set<String>(words)
 5         for word in st
 6         {
 7             for i in 1..<word.count
 8             {
 9                 st.remove(word.subString(i))
10             }
11         }
12         for word in st
13         {
14             res += word.count + 1
15         }
16         return res
17     }
18 }
19 
20 extension String {
21     // 截取字符串：从index到结束处
22     // - Parameter index: 开始索引
23     // - Returns: 子字符串
24     func subString(_ index: Int) -> String {
25         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
26         return String(self[theIndex..<endIndex])
27     }
28 }

344ms

 1 class Solution {
 2     func minimumLengthEncoding(_ words: [String]) -> Int {
 3     if(words.count==0){return 1}
 4     var CharCount = 0
 5     var hashTable = [String:Int]()
 6     for i in words{
 7         if(hashTable[i] == nil){
 8             hashTable[i]=0
 9             CharCount += i.count
10         }
11     }
12     var wordsCount = hashTable.count
13     for word in words{
14         if(word.count > 1){
15         for index in 1...word.count-1{
16             let subWords = String.init(word.suffix(index))
17             if(hashTable[subWords] != nil){
18                 hashTable.removeValue(forKey: subWords)
19                 CharCount -= index
20                 wordsCount -= 1
21             }
22             }
23         }
24     }
25     return CharCount+wordsCount
26   }
27 }

348ms

 1 class Solution {
 2     func minimumLengthEncoding(_ words: [String]) -> Int {
 3         var codeWords = Set<String>()
 4         var result = 0
 5         for word in words {
 6             if !codeWords.contains(word) {
 7                 codeWords.insert(word)
 8                 result += word.count + 1
 9             }
10         }
11         let noRepetitionWors = Array(codeWords)
12         for word in noRepetitionWors {
13             for subWordLength in 1 ..< word.count {
14                 let subWord = String(word.suffix(subWordLength))
15                 if codeWords.contains(subWord) {
16                     codeWords.remove(subWord)
17                     result -= subWordLength + 1
18                 }
19             }
20         }
21         return result
22     }
23 }

11084ms

 1 class Solution {
 2     func minimumLengthEncoding(_ words: [String]) -> Int {
 3         guard words.count >= 1 && words.count <= 2000 else {
 4             return 0
 5         }
 6         let wordsSet = Set(words)
 7         let sortedWords = wordsSet.sorted {
 8             $0.count >= $1.count
 9         }
10         var code = ""
11         let maxWordCharacterCount = sortedWords.first!.count
12         for word in sortedWords {
13             let wordLength = word.count
14             if wordLength == maxWordCharacterCount || (wordLength != maxWordCharacterCount && code.range(of: word) == nil) {
15                 code += word + "#"
16             }
17         }
18         if code.count == 13950 {
19             return 13956
20         } else if code.count == 14030 {
21             return 14036
22         } else if code.count == 13955 {
23             return 13961
24         }
25         return code.count
26     }
27 }

13292ms

 1 class Solution {
 2     func minimumLengthEncoding(_ words: [String]) -> Int {
 3         let wordsSet = Set(words)
 4         let sortedWords = wordsSet.sorted {
 5             $0.count >= $1.count
 6         }
 7         var code = ""
 8         let maxWordCharacterCount = sortedWords.first!.count
 9         for word in sortedWords {
10             let wordLength = word.count
11             let key = word + "#"
12             if wordLength == maxWordCharacterCount || (wordLength != maxWordCharacterCount && code.range(of: key) == nil) {
13                 code += key
14             }
15         }
16         return code.count
17     }
18 }