#P3080. 一种字符串压缩表示的解压(100分)
-
1000ms
Tried: 164
Accepted: 31
Difficulty: 3
所属公司 :
华为od
一种字符串压缩表示的解压(100分)
题面解释:
有一种简易压缩算法,针对全部由小写英文字母组成的字符串,将其中连续超过两个相同字母的部分压缩为连续个数加该字母,其他部分保持原样不变。例如,字符串“aaabbccccd”经过压缩成为字符串“3abb4cd”。现要求编写一个解压函数,根据输入的字符串判断其是否为合法的压缩过的字符串。输入为一个长度不超过100个字符的ASCII字符串,输出如果输入合法则为解压缩后的字符串,若输入不合法则输出字符串“!error”来报告错误。用例保证输出的字符串长度也不会超过100个字符。
题解:
按照题意模拟即可,注意压缩两次后还要跟原来一样,比如3ddd一次压缩后是dddddd但是二次压缩就是6d与原来不同所以不符合.
要解决这个问题,我们需要完成以下几个步骤:
-
解析并解压缩输入字符串:
- 遍历输入字符串,逐个字符检查。
- 如果遇到数字,解析完整的数字(可能是多位数),然后检查其后的字符是否为小写字母。
- 确保数字表示的次数至少为3,因为只有连续超过两个相同字母才会被压缩。
- 根据解析出的数字和字母,生成相应数量的字母并添加到结果字符串中。
- 如果当前字符不是数字,则直接将其添加到结果字符串中,前提是它是小写字母。
-
验证解压后的字符串是否符合压缩规则:
- 为了确保输入字符串是合法的压缩字符串,我们需要将解压后的字符串重新压缩,并与原始输入进行比较。
- 如果重新压缩后的字符串与原始输入相同,则输入合法,输出解压后的字符串。
- 否则,输入不合法,输出“
!error”。
-
错误处理:
- 输入字符串中只能包含数字和小写字母。
- 压缩格式必须正确,即数字后必须跟着一个小写字母,且数字表示的次数必须至少为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,故输入不合法。