刷题笔记合集🔗

一种字符串压缩表示的解压

问题描述

有一种简易压缩算法：针对全部由小写英文字母组成的字符串，将其中连续超过两个相同字母的部分压缩为连续个数加该字母，其他部分保持原样不变。

例如：字符串 "aaabbccccd" 经过压缩成为字符串 "3abb4cd"。

请您编写解压函数，根据输入的字符串，判断其是否为合法压缩过的字符串，若输入合法则输出解压缩后的字符串，否则输出字符串 "!error " 来报告错误。

输入格式

输入一行，为一个 ASCII 字符串，长度不会超过 字符，用例保证输出的字符串长度也不会超过 字符。

输出格式

若判断输入为合法的经过压缩后的字符串，则输出压缩前的字符串；

若输入不合法，则输出字符串 "!error "。

样例输入

4dff

2dff

4d@A

样例输出

ddddff

!error

!error

数据范围

• 输入字符串长度不超过 字符
• 输出字符串长度不超过 字符
• 输入字符串为 ASCII 字符

题解

这道题目要求我们解压一种特殊格式的压缩字符串，并验证其合法性。首先需要理解这种压缩算法的规则：

1. 只对连续超过两个的相同字母进行压缩，变成"数量+字母"的形式
2. 其他部分保持不变
3. 原始字符串只由小写英文字母组成

解题的关键点在于：

1. 验证输入字符串是否只包含小写字母和数字
2. 解析压缩格式，如"4d"需要转换为"dddd"
3. 验证解压后的字符串再次压缩是否能得到原始输入

解压过程中需要注意的几个特殊情况：

• 数字后面必须跟着小写字母，否则不合法
• 数字必须大于等于3，因为只有连续超过2个的字母才会被压缩
• 解压后的字符串再次压缩必须与原字符串一致，否则说明原压缩格式不合法

我采用了正则表达式来匹配压缩字符串中的"数字+字母"模式。对于匹配到的每个模式，验证其合法性并将其替换为对应的重复字母。

举个例子分析：

• 输入 "4dff"：验证合法性 → 解压为 "ddddff" → 再次压缩为 "4dff" → 与原字符串相同，输出 "ddddff"
• 输入 "2dff"：数字 2 小于 3，不合法，输出 "!error"
• 输入 "3bb"：解压为 "bbbb" → 再次压缩为 "4b" → 与原字符串不同，输出 "!error"

时间复杂度：每次处理一个"数字+字母"模式的替换操作，最坏情况下可能需要O(n)时间，总体时间复杂度为O(n²)，其中n为字符串长度。对于题目给定的长度不超过100的字符串，这个复杂度是可以接受的。

参考代码

• Python

import sys

def compress(s: str) -> str:
    """
    将原始字符串 s 按照规则压缩：
      - 连续相同字符超过 2 个时，替换成 "数量+字符"
      - 否则保留原样
    """
    if not s:
        return ""
    res = []
    prev = s[0]      # 当前扫描到的字符
    count = 1        # 计数

    # 从第二个字符开始遍历
    for ch in s[1:]:
        if ch == prev:
            count += 1
        else:
            # 当字符组结束时，决定是数字+字母还是原样输出
            if count > 2:
                res.append(f"{count}{prev}")
            else:
                res.append(prev * count)
            prev = ch
            count = 1

    # 处理最后一组
    if count > 2:
        res.append(f"{count}{prev}")
    else:
        res.append(prev * count)

    return "".join(res)


def decompress(s: str) -> str:
    """
    解压函数。输入 s 为可能的压缩字符串，返回：
      - 解压后的字符串（如果合法）
      - "!error" （输入非法）
    合法性判定要点：
      1. 数字要跟在一起，并且后面一定要有小写字母
      2. 数字值 >= 3
      3. 解压后重新压缩，必须和原串一致
    """
    n = len(s)
    i = 0
    output = []

    while i < n:
        ch = s[i]
        if ch.isdigit():
            # 先读取完整的数字部分
            j = i
            while j < n and s[j].isdigit():
                j += 1
            num_str = s[i:j]

            # 数字后面必须有且只有一个小写字母
            if j >= n or not s[j].islower():
                return "!error"
            count = int(num_str)
            if count < 3:
                return "!error"

            # 重复该字母 count 次
            output.append(s[j] * count)
            i = j + 1

        elif ch.islower():
            # 普通单个小写字母
            output.append(ch)
            i += 1
        else:
            # 遇到非法字符
            return "!error"

    decompressed = "".join(output)

    # 再次压缩结果，必须和原输入一致
    if compress(decompressed) != s:
        return "!error"
    return decompressed


def main():
    s = sys.stdin.readline().strip()
    # 全局检查：只能出现数字和小写字母
    if any(not (c.isdigit() or c.islower()) for c in s):
        print("!error")
    else:
        print(decompress(s))


if __name__ == "__main__":
    main()

# —— 样例测试 —— 
# 示例 1:
# 输入：4dff
# 输出：ddddff
#
# 示例 2:
# 输入：2dff
# 输出：!error
#
# 示例 3:
# 输入：4d@A
# 输出：!error

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 按规则压缩字符串：连续相同字符超过 2 个时，输出 "数量+字符"，否则原样输出
string compressStr(const string &s) {
    if (s.empty()) return "";
    string result;
    char prev = s[0];
    int count = 1;

    for (int