E卷-简易压缩算法-一种字符串压缩表示的解压-(200p)

简易压缩算法-一种字符串压缩表示的解压

问题描述

卢小姐发明了一种简单的字符串压缩方法：对于由小写英文字母组成的字符串，将连续出现超过两次的字母压缩为"出现次数+该字母"的形式，其他部分保持不变。例如，"aaabbccccd" 压缩后变为 "3abb4cd"。

现在，卢小姐需要一个解压缩程序。你能帮她编写一个函数，判断输入的字符串是否为有效的压缩字符串，并在有效时输出解压缩后的结果吗？

输入格式

输入为一行字符串，长度不超过 100 个字符。

输出格式

如果输入是有效的压缩字符串，输出解压缩后的原始字符串。 如果输入无效，输出 "!error"。

样例输入

4dff

样例输出

ddddff

样例解释

"4d" 解压缩为 "dddd"，因此完整的解压缩结果为 "ddddff"。

样例输入

2dff

样例输出

!error

样例解释

两个连续的 'd' 不需要压缩，因此输入无效。

样例输入

4d@A

样例输出

!error

样例解释

压缩字符串中不应出现特殊字符 '@' 和大写字母 'A'，因此输入无效。

数据范围

• 输入字符串长度不超过 100。
• 解压缩后的字符串长度也不超过 100。

题解

解决这个问题的关键在于正确识别和处理压缩字符串。主要步骤如下：

1. 验证输入字符串的合法性：

   • 只包含小写字母和数字。
   • 数字后面必须跟着一个小写字母。
   • 单个或两个连续的小写字母不应该被压缩。

2. 解压缩字符串：

   • 使用正则表达式匹配数字和字母的组合。
   • 将匹配到的组合展开为重复的字母。

3. 验证解压缩结果：

   • 将解压缩后的字符串重新压缩。
   • 比较重新压缩的结果与原始输入是否一致。

4. 输出结果：

   • 如果验证通过，输出解压缩的字符串。
   • 否则，输出 "!error"。

参考代码

• Python

import re

def decompress(s):
    # 检查输入是否只包含小写字母和数字
    if not re.match(r'^[a-z1-9]+$', s):
        return '!error'
    
    def compress(text):
        # 压缩函数：将连续重复3次及以上的字符替换为数字+字符
        return re.sub(r'(.)\1{2,}', lambda m: str(len(m.group(0))) + m.group(1), text)
    
    def expand(text):
        # 解压函数：将数字+字符的形式展开为重复的字符
        result = ''
        i = 0
        while i < len(text):
            if text[i].isdigit():
                j = i
                while j < len(text) and text[j].isdigit():
                    j += 1
                if j == len(text) or not text[j].isalpha():
                    return '!error'  # 数字后面必须跟着一个字母
                count = int(text[i:j])
                if count < 3:
                    return '!error'  # 压缩的数量必须至少为3
                result += text[j] * count
                i = j + 1
            else:
                result += text[i]
                i += 1
        return result
    
    # 解压输入字符串
    expanded = expand(s)
    if expanded == '!error':
        return '!error'
    
    # 检查解压后再压缩是否与原字符串相同
    if compress(expanded) != s:
        return '!error'
    
    return expanded

# 读取输入并输出结果
s = input().strip()
print(decompress(s))

• Java

import java.util.Scanner;
import java.util.regex.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine().trim();
        System.out.println(decompress(s));
        scanner.close();
    }

    public static String decompress(String s) {
        // 检查输入是否只包含小写字母和数字
        if (!s.matches("^[a-z1-9]+$")) {
            return "!error";