题面解释:

有一种简易压缩算法，针对全部由小写英文字母组成的字符串，将其中连续超过两个相同字母的部分压缩为连续个数加该字母，其他部分保持原样不变。例如，字符串“aaabbccccd”经过压缩成为字符串“3abb4cd”。现要求编写一个解压函数，根据输入的字符串判断其是否为合法的压缩过的字符串。输入为一个长度不超过100个字符的ASCII字符串，输出如果输入合法则为解压缩后的字符串，若输入不合法则输出字符串“!error”来报告错误。用例保证输出的字符串长度也不会超过100个字符。

题解:

按照题意模拟即可，注意压缩两次后还要跟原来一样，比如$3ddd$一次压缩后是$dddddd$但是二次压缩就是$6d$与原来不同所以不符合.

要解决这个问题，我们需要完成以下几个步骤：

1. 解析并解压缩输入字符串：

   • 遍历输入字符串，逐个字符检查。
   • 如果遇到数字，解析完整的数字（可能是多位数），然后检查其后的字符是否为小写字母。
   • 确保数字表示的次数至少为3，因为只有连续超过两个相同字母才会被压缩。
   • 根据解析出的数字和字母，生成相应数量的字母并添加到结果字符串中。
   • 如果当前字符不是数字，则直接将其添加到结果字符串中，前提是它是小写字母。

2. 验证解压后的字符串是否符合压缩规则：

   • 为了确保输入字符串是合法的压缩字符串，我们需要将解压后的字符串重新压缩，并与原始输入进行比较。
   • 如果重新压缩后的字符串与原始输入相同，则输入合法，输出解压后的字符串。
   • 否则，输入不合法，输出“!error”。

3. 错误处理：

   • 输入字符串中只能包含数字和小写字母。
   • 压缩格式必须正确，即数字后必须跟着一个小写字母，且数字表示的次数必须至少为3。
   • 如果遇到任何不符合上述条件的情况，则输出“!error”。

时间复杂度分析

• 解压缩函数 decompress：

  • 遍历输入字符串一次，时间复杂度为 O(N)，其中 N 是输入字符串的长度。

• 压缩函数 compress：

  • 遍历解压后的字符串一次，时间复杂度为 O(M)，其中 M 是解压后字符串的长度。

• 整体时间复杂度：

  • 解压缩和压缩各自为线性时间，总体时间复杂度为 O(N + M)。
  • 由于输入和输出字符串的长度均不超过100字符，因此在实际运行中，时间复杂度可视为常数时间，表现为高效。

c++

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

// 函数用于解压缩输入字符串
bool decompress(const string& input, string& output) {
    int i = 0;
    int n = input.length();
    output = "";
    
    while(i < n){
        if(isdigit(input[i])){
            // 解析数字
            int num = 0;
            while(i < n && isdigit(input[i])){
                num = num * 10 + (input[i] - '0');
                i++;
            }
            // 检查是否有字母跟随
            if(i >= n || !islower(input[i])){
                return false;
            }
            // 检查数字是否大于等于3
            if(num < 3){
                return false;
            }
            // 添加解压后的字母
            char letter = input[i];
            for(int j = 0; j < num; j++){
                output += letter;
            }
            i++; // 移动到下一个字符
        }
        else{
            // 检查是否是小写字母
            if(!islower(input[i])){
                return false;
            }
            // 添加普通字母
            output += input[i];
            i++;
        }
    }
    
    return true;
}

// 函数用于重新压缩解压后的字符串
string compress(const string& s){
    string compressed = "";
    int n = s.length();
    int i = 0;
    
    while(i < n){
        int count = 1;
        while(i + count < n && s[i + count] == s[i]){
            count++;
        }
        if(count > 2){
            compressed += to_string(count) + (char)s[i];
        }
        else{
            for(int j = 0; j < count; j++) {
                compressed += s[i];
            }
        }
        i += count;
    }
    
    return compressed;
}

int main(){
    string input;
    cin >> input;
    string decompressed;
    
    // 解压缩并验证
    if(!decompress(input, decompressed)){
        cout << "!error";
        return 0;
    }
    
    // 重新压缩解压后的字符串
    string recompressed = compress(decompressed);
    
    // 比较重新压缩的结果与原始输入
    if(recompressed == input){
        cout << decompressed;
    }
    else{
        cout << "!error";
    }
    
    return 0;
}

python

import sys

def decompress(input_str):
    output = ""
    i = 0
    n = len(input_str)
    
    while i < n:
        if input_str[i].isdigit():
            # 解析数字
            num = 0
            while i < n and input_str[i].isdigit():
                num = num * 10 + int(input_str[i])
                i += 1
            # 检查是否有字母跟随
            if i >= n or not input_str[i].islower():
                return False, ""
            # 检查数字是否大于等于3
            if num < 3:
                return False, ""
            # 添加解压后的字母
            letter = input_str[i]
            output += letter * num
            i += 1  # 移动到下一个字符
        else:
            # 检查是否是小写字母
            if not input_str[i].islower():
                return False, ""
            # 添加普通字母
            output += input_str[i]
            i += 1
    
    return True, output

def compress(s):
    compressed = ""
    n = len(s)
    i = 0
    
    while i < n:
        count = 1
        while (i + count < n) and (s[i + count] == s[i]):
            count += 1
        if count > 2:
            compressed += str(count) + s[i]
        else:
            compressed += s[i] * count
        i += count
    
    return compressed

def main():
    input_str = sys.stdin.read().strip()
    valid, decompressed = decompress(input_str)
    
    if not valid:
        print("!error")
        return
    
    recompressed = compress(decompressed)
    
    if recompressed == input_str:
        print(decompressed)
    else:
        print("!error")

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {

    // 解压缩函数
    public static boolean decompress(String input, StringBuilder output) {
        int i = 0;
        int n = input.length();
        
        while (i < n) {
            if (Character.isDigit(input.charAt(i))) {
                // 解析数字
                int num = 0;
                while (i < n && Character.isDigit(input.charAt(i))) {
                    num = num * 10 + (input.charAt(i) - '0');
                    i++;
                }
                // 检查是否有字母跟随
                if (i >= n || !Character.isLowerCase(input.charAt(i))) {
                    return false;
                }
                // 检查数字是否大于等于3
                if (num < 3) {
                    return false;
                }
                // 添加解压后的字母
                char letter = input.charAt(i);
                for (int j = 0; j < num; j++) {
                    output.append(letter);
                }
                i++; // 移动到下一个字符
            } else {
                // 检查是否是小写字母
                if (!Character.isLowerCase(input.charAt(i))) {
                    return false;
                }
                // 添加普通字母
                output.append(input.charAt(i));
                i++;
            }
        }
        
        return true;
    }

    // 压缩函数
    public static String compress(String s) {
        StringBuilder compressed = new StringBuilder();
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            int count = 1;
            while (i + count < n && s.charAt(i + count) == s.charAt(i)) {
                count++;
            }
            if (count > 2) {
                compressed.append(count).append(s.charAt(i));
            } else {
                for (int j = 0; j < count; j++) {
                    compressed.append(s.charAt(i));
                }
            }
            i += count;
        }
        
        return compressed.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        scanner.close();
        
        StringBuilder decompressed = new StringBuilder();
        
        // 解压缩并验证
        boolean valid = decompress(input, decompressed);
        if (!valid) {
            System.out.println("!error");
            return;
        }
        
        // 重新压缩解压后的字符串
        String recompressed = compress(decompressed.toString());
        
        // 比较重新压缩的结果与原始输入
        if (recompressed.equals(input)) {
            System.out.println(decompressed.toString());
        } else {
            System.out.println("!error");
        }
    }
}

题目内容

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

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

请您编写解压函数，根据输入的字符串，判断其是否为合法压缩过的字符串，

若输入合法则输出解压缩后的字符串，否则输出字符串“$!error$”来报告错误。

输入描述

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

输出描述

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

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

样例1

输入

4dff

输出

ddddff

说明

$4d$扩展为$dddd$，故解压后的字符串为$ddddff$。

样例2

输入

2dff

输出

!error

说明

两个$d$不需要压缩，故输入不合法。

样例3

输入

4d@A

输出

!error

说明

全部由小写英文字母组成的字符串压缩后不会出现特殊字符$@$和大写字母$A$，故输入不合法。