【压缩字符串算法解析与实现】

压缩的要求是将连续相同字符替换为字符 + 数字形式，例如 “AAABCCDDDD” 变为 “A3BC2D4”。

问题描述与分析

给定一个字符串，我们需要判断是否可以进行压缩，并且只在压缩后的字符串长度比原字符串长度更短时进行压缩。如果字符串可以压缩，则输出压缩后的字符串，否则输出 “NO”。

解决方案

算法思路

通过遍历字符串的每个字符来实现该算法，需要维护一个计数器，用于统计连续相同字符的个数。当遇到一个不同的字符时，我们将之前的字符及其计数器添加到压缩后的字符串中，并将计数器重置为 1。

实现步骤

1. 遍历字符串的每个字符，并初始化一个计数器为 1。
2. 对于每个字符，如果当前字符与下一个字符相同，则增加计数器；如果不同，则将当前字符及其计数器添加到压缩后的字符串中，并将计数器重置为 1。
3. 判断压缩后的字符串是否比原字符串短，如果是，则输出压缩后的字符串；否则输出 “NO”。

代码实现

#include <iostream>
#include <string>int main() {std::string s;std::cin >> s;std::string compressedString;int count = 1;for (int i = 0; i < s.length(); ++i) {if (i + 1 < s.length() && s[i] == s[i + 1]) {// 如果当前字符与下一个字符相同，则增加计数器count++;} else {// 如果当前字符与下一个字符不同，则将当前字符及其计数器添加到压缩后的字符串中compressedString += s[i];if (count > 1) {compressedString += std::to_string(count); // 将计数器转换为字符串添加到压缩后的字符串中}count = 1; // 重置计数器}}// 判断压缩后的字符串是否比原字符串短if (compressedString.length() < s.length()) {std::cout << compressedString << std::endl;} else {std::cout << "NO" << std::endl;}return 0;
}