820. Short Encoding of Words

发表于 | 分类于 | |

820. Short Encoding of Words

题目描述

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:

1
2
3
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

题目大意

给定一组单词将字符变为 word1#word2#....wordn 的字符串 S。
对于任意单词，从下标 i 到 S 中最近的一个 # 之间的，部分相等，则可以不计算此单词。

解题思路

将 words 中的单词反转之后进行排序，如果下一单词不是上一单词的前缀，则加上下一单词的字符长度和 # 字符的长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func minimumLengthEncoding(_ words: [String]) -> Int {
        var ans = 0
        var last = ""
        for word in (words.map{ String($0.reversed())}.sorted{$0 > $1} + [""]){
            if !last.hasPrefix(word) {
                ans += word.count + 1
            }
            last = word
        }
        return ans
    }
}
0%