刷题笔记合集🔗

问题描述

小兰负责开发一个文本压缩系统。系统使用一种简单的压缩算法：对于全部由小写英文字母组成的字符串，将其中连续超过两个相同字母的部分压缩为"连续个数+该字母"的形式，其他部分保持原样不变。

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

现在请你帮助小兰编写解压函数，判断输入的字符串是否为合法的压缩字符串。如果合法则输出解压后的原始字符串，否则输出 "!error"。

输入格式

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

输出格式

如果输入是合法的压缩字符串，输出解压后的原始字符串； 如果输入不合法，输出 "!error"。

样例输入1

4dff

样例输出1

ddddff

样例输入2

2dff

样例输出2

!error

样例输入3

4d@A

样例输出3

!error

样例输入4

3bb

样例输出4

!error

样例解释

数据范围

• 输入字符串长度不超过 100
• 解压后的字符串长度不超过 100
• 压缩数字 满足

题解

这是一道字符串处理题目,主要考察以下几个关键点:

1. 合法性判断

• 只能包含小写字母和数字
• 压缩数字必须大于等于3
• 数字后面必须跟着字母

2. 解压缩过程

• 使用正则表达式匹配"数字+字母"模式
• 将匹配到的部分替换为重复字母
• 注意替换时只替换第一次匹配

3. 验证过程

• 将解压后的字符串重新压缩
• 检查是否与输入字符串相同
• 不同则说明输入不合法

时间复杂度:

• 解压缩过程 O(n)
• 重新压缩验证 O(n)
• 总体复杂度 O(n)

参考代码

import re

def decompress(s):
    # 备份原始字符串
    orig = s
    
    # 检查是否只包含小写字母和数字
    if re.search(r'[^a-z0-9]', s):
        return '!error'
    
    # 匹配数字+字母模式
    pat = re.compile(r'(\d+)([a-z])?')
    
    while True:
        m = pat.search(s)
        if not m:
            break
            
        # 获取匹配部分
        src = m.group()
        cnt = int(m.group(1))
        ch = m.group(2)
        
        # 验证合法性
        if cnt < 3 or not ch:
            return '!error'
            
        # 替换第一次匹配
        s = s.replace(src, ch * cnt, 1)
    
    # 重新压缩验证
    if compress(s) != orig:
        return '!error'
        
    return s

def compress(s):
    s += '-'  # 哨兵
    res = []
    cnt = 1
    
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            cnt += 1
        else:
            if cnt > 2:
                res.append(f'{cnt}{s[i-1]}')
            else:
                res.append(s[i-1] * cnt)
            cnt = 1
            
    return ''.join(res)

# 处理输入
print(decompress(input()))

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

// 压缩字符串
string compress(string s) {
    s += '-';  // 哨兵
    string res;
    int cn