题目描述

实现一个算法来压缩一个字符串。压缩的要求如下：需要判断压缩能不能节省空间，仅在压缩后字符串比原字符串长度更短时进行压缩。压缩的格式是将连续相同字符替换为字符 + 数字形式，例如 "AAABCCDDDD" 变为 "A3BC2D4"。

输入描述

输入一行字符串，长度不超过 500.

输出描述

输出一行。若输入的字符串可压缩，则输出压缩后的字符串，否则输出 NO。

输入输出样例

示例

输入

AAABCCDDDD

输出

A3BC2D4

运行限制

最大运行时间：1s

最大运行内存: 256M

解题思路

#include <iostream>
using namespace std;
int main()
{
    // 定义两个字符串变量s s2
    string s, s2;
    cin >> s;

    int num = 1; // 相同字母的长度
    int len = s.size(); // 获取输入的字符串的长度
    // for 循环开始遍历字符串
    for (int i = 0; i < len; i++)
    {
        
        if ((i + 1 < len) && s[i] == s[i + 1])
        {
            num++;
        }
        else
        { // 如果不相等，将当前字母加在新串后
            s2 += s[i];
            if (num > 1)              // 如果相同字母大于1，则加上这个数字
                s2 += to_string(num); // to_string()将数字转字符串
            num = 1;                  // 下一个相同长度重置为1
        }
    }

    int l1 = s.size(), l2 = s2.size();
    if (l1 > l2)
        cout << s2;
    else
        cout << "NO";
    return 0;
}

首先是声明变量并初始化，s: 输入的字符串；s2: 存储压缩后的字符串；num: 用于记录当前连续相同字符的数量，初始值为 1；len: 存储字符串 s 的长度，用于遍历字符串。

然后使用 for 循环来遍历输入的字符串，每次处理一个字符。 在处理字符串的每一个字符时候，检查判断相邻字符是否相等。

if ((i + 1 < len) && s[i] == s[i + 1]) {
    num++;
}

如果当前字符 s[i] 和下一个字符 s[i + 1] 相等，说明有连续的相同字符，那么就将计数器 num 加 1。通过使用 i + 1 < len 确保不会越界访问 s[i + 1]；s[i] == s[i + 1] 判断当前字符是否与下一个字符相同。

然后需要处理不相同的情况：

else {
    s2 += s[i]; // 将当前字符添加到压缩后的字符串中

    if (num > 1) // 如果连续字符数量大于 1
        s2 += to_string(num); // 将数字转换为字符串并添加到 s2 中

    num = 1; // 重置计数器
}

如果检查发现字符不连续时候，s2 += s[i] 将当前字符 s[i] 添加到压缩后的字符串 s2 中，if (num > 1): 检查连续字符数量是否大于 1，如果大于1那么就将计数值转换为字符串并追加到 s2 后，重置计数器 num 为 1，准备处理下一个字符。

int l1 = s.size(), l2 = s2.size();
if (l1 > l2)
    cout << s2; // 如果压缩后的字符串更短，输出压缩结果
else
    cout << "NO"; // 否则输出 "NO"

再最后比较压缩后和原字符串的长度，检查输入的字符串是否已经被压缩了，获取压缩前字符串长度和压缩后的字符串长度，如果压缩前的字符串长度大于压缩后的就打印压缩结果，否则就直接打印NO。