题目描述
给定一个字符串 compressed 表示一个字符串的压缩版本。格式是一个字符后面加上其出现频率。例如 "a3b1a1c2" 是字符串 "aaabacc" 的一个压缩版本。
我们在以下条件下寻求 更好的压缩：
- 每个字符在压缩版本中只应出现 一次。
- 字符应按 字母顺序 排列。
返回 compressed 的更好压缩版本。
注意：在更好的压缩版本中，字母的顺序可能会改变，这是可以接受的。
示例 1：
输入：compressed = "a3c9b2c1"
输出："a3b2c10"
解释：
字符 "a" 和 "b" 在输入中只出现了一次，但 "c" 出现了两次，第一次长度为 9，另一次是长度为 1。
因此，在结果字符串中，它应当长度为 10。
示例 2：
输入：compressed = "c2b3a1"
输出："a1b3c2"
示例 3：
输入：compressed = "a2b4c1"
输出："a2b4c1"
提示：
1 <= compressed.length <= 6 * 104compressed 仅由大写英文字母和数字组成。compressed 是有效的压缩，即，每个字符后面都有其出现频率。- 出现频率在
[1, 104] 之间并且没有前导 0。
解法
方法一：哈希表 + 双指针
我们可以使用哈希表来统计每个字符的频率，然后使用双指针来遍历 compressed 字符串，将每个字符的频率累加到哈希表中，最后按照字母顺序将字符和频率拼接成字符串。
时间复杂度 $O(n + |\Sigma| \log |\Sigma|)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 compressed 的长度，而 $|\Sigma|$ 是字符集的大小，这里字符集是小写字母，所以 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def betterCompression(self, compressed: str) -> str:
cnt = Counter()
i, n = 0, len(compressed)
while i < n:
j = i + 1
x = 0
while j < n and compressed[j].isdigit():
x = x * 10 + int(compressed[j])
j += 1
cnt[compressed[i]] += x
i = j
return "".join(sorted(f"{k}{v}" for k, v in cnt.items()))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public String betterCompression(String compressed) {
Map<Character, Integer> cnt = new TreeMap<>();
int i = 0;
int n = compressed.length();
while (i < n) {
char c = compressed.charAt(i);
int j = i + 1;
int x = 0;
while (j < n && Character.isDigit(compressed.charAt(j))) {
x = x * 10 + (compressed.charAt(j) - '0');
j++;
}
cnt.merge(c, x, Integer::sum);
i = j;
}
StringBuilder ans = new StringBuilder();
for (var e : cnt.entrySet()) {
ans.append(e.getKey()).append(e.getValue());
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
string betterCompression(string compressed) {
map<char, int> cnt;
int i = 0;
int n = compressed.length();
while (i < n) {
char c = compressed[i];
int j = i + 1;
int x = 0;
while (j < n && isdigit(compressed[j])) {
x = x * 10 + (compressed[j] - '0');
j++;
}
cnt[c] += x;
i = j;
}
stringstream ans;
for (const auto& entry : cnt) {
ans << entry.first << entry.second;
}
return ans.str();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func betterCompression(compressed string) string {
cnt := map[byte]int{}
n := len(compressed)
for i := 0; i < n; {
c := compressed[i]
j := i + 1
x := 0
for j < n && compressed[j] >= '0' && compressed[j] <= '9' {
x = x*10 + int(compressed[j]-'0')
j++
}
cnt[c] += x
i = j
}
ans := strings.Builder{}
for c := byte('a'); c <= byte('z'); c++ {
if cnt[c] > 0 {
ans.WriteByte(c)
ans.WriteString(strconv.Itoa(cnt[c]))
}
}
return ans.String()
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | function betterCompression(compressed: string): string {
const cnt = new Map<string, number>();
const n = compressed.length;
let i = 0;
while (i < n) {
const c = compressed[i];
let j = i + 1;
let x = 0;
while (j < n && /\d/.test(compressed[j])) {
x = x * 10 + +compressed[j];
j++;
}
cnt.set(c, (cnt.get(c) || 0) + x);
i = j;
}
const keys = Array.from(cnt.keys()).sort();
const ans: string[] = [];
for (const k of keys) {
ans.push(`${k}${cnt.get(k)}`);
}
return ans.join('');
}
|