Skip to content

Latest commit

 

History

History
227 lines (180 loc) · 6.13 KB

README.md

File metadata and controls

227 lines (180 loc) · 6.13 KB
comments difficulty edit_url tags
true
中等
哈希表
字符串
计数
排序

3167. 字符串的更好压缩 🔒

English Version

题目描述

给定一个字符串 compressed 表示一个字符串的压缩版本。格式是一个字符后面加上其出现频率。例如 "a3b1a1c2" 是字符串 "aaabacc" 的一个压缩版本。

我们在以下条件下寻求 更好的压缩：

  1. 每个字符在压缩版本中只应出现 一次。
  2. 字符应按 字母顺序 排列。

返回 compressed 的更好压缩版本。

注意：在更好的压缩版本中，字母的顺序可能会改变，这是可以接受的。

 

示例 1：

输入：compressed = "a3c9b2c1"

输出："a3b2c10"

解释：

字符 "a" 和 "b" 在输入中只出现了一次，但 "c" 出现了两次，第一次长度为 9，另一次是长度为 1。

因此，在结果字符串中，它应当长度为 10。

示例 2：

输入：compressed = "c2b3a1"

输出："a1b3c2"

示例 3：

输入：compressed = "a2b4c1"

输出："a2b4c1"

 

提示：

  • 1 <= compressed.length <= 6 * 104
  • compressed 仅由大写英文字母和数字组成。
  • compressed 是有效的压缩，即，每个字符后面都有其出现频率。
  • 出现频率在 [1, 104] 之间并且没有前导 0。

解法

方法一：哈希表 + 双指针

我们可以使用哈希表来统计每个字符的频率，然后使用双指针来遍历 compressed 字符串，将每个字符的频率累加到哈希表中，最后按照字母顺序将字符和频率拼接成字符串。

时间复杂度 $O(n + |\Sigma| \log |\Sigma|)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 compressed 的长度，而 $|\Sigma|$ 是字符集的大小，这里字符集是小写字母，所以 $|\Sigma| = 26$。

Python3

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()))

Java

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();
    }
}

C++

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();
    }
};

Go

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()
}

TypeScript

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('');
}