题解 | #字符串压缩算法#

题目链接

字符串压缩算法

题目描述

输入一串字符，请编写一个字符串压缩程序，将字符串中连续出现的重复字母进行压缩，并输出压缩后的字符串。

例如：

aac 压缩为 1ac
xxxxyyyyyyzbbb 压缩为 3x5yz2b

解题思路

这是一个字符串处理问题，核心在于遍历字符串并对连续相同的字符进行计数和编码。通过分析题目给出的示例，我们可以推导出特殊的压缩规则：

规则推导：
- xxxxyyyyyyzbbb -> 3x5yz2b
- xxxx (4个'x') -> 3x
- yyyyyy (6个'y') -> 5y
- z (1个'z') -> z
- bbb (3个'b') -> 2b
- aac -> 1ac
- aa (2个'a') -> 1a
- c (1个'c') -> c
从以上示例可以看出，如果一个字符 c 连续出现了 n 次：
- 当 n > 1 时，它被压缩为数字 n-1 加上字符 c。
- 当 n = 1 时，它保持原样，只输出字符 c。

算法流程（双指针法）：

初始化：创建一个 StringBuilder 或类似的可变字符串 result 用于存放压缩后的结果。使用一个指针 i 从头开始遍历输入字符串。
遍历与计数：
- 当指针 i 未越界时，进入循环。
- 记录下当前字符 currentChar = s[i]。
- 使用另一个指针 j 从 i 开始向后查找，统计 currentChar 连续出现的次数 count。j 一直移动到字符串末尾或遇到一个不同的字符为止。
编码与追加：
- 计数结束后，我们得到了连续字符 currentChar 的数量 count。
- 根据推导出的规则：
  - 如果 count > 1，将 count - 1 和 currentChar 追加到 result 中。
  - 如果 count == 1，只将 currentChar 追加到 result 中。
更新指针：
- 将外层循环的指针 i 更新为 j 的位置，以便从下一个新的字符开始下一轮计数。
循环直到结束：重复步骤 2-4，直到指针 i 遍历完整个字符串。最终 result 中的内容就是答案。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    getline(cin, s);

    if (s.empty()) {
        cout << "" << endl;
        return 0;
    }

    stringstream result;
    int n = s.length();
    int i = 0;
    while (i < n) {
        char current_char = s[i];
        int count = 0;
        int j = i;
        while (j < n && s[j] == current_char) {
            count++;
            j++;
        }

        if (count > 1) {
            result << (count - 1) << current_char;
        } else {
            result << current_char;
        }
        i = j;
    }

    cout << result.str() << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        if (s == null || s.isEmpty()) {
            System.out.println("");
            return;
        }

        StringBuilder result = new StringBuilder();
        int n = s.length();
        int i = 0;
        while (i < n) {
            char currentChar = s.charAt(i);
            int count = 0;
            int j = i;
            while (j < n && s.charAt(j) == currentChar) {
                count++;
                j++;
            }

            if (count > 1) {
                result.append(count - 1);
                result.append(currentChar);
            } else {
                result.append(currentChar);
            }
            i = j;
        }

        System.out.println(result.toString());
    }
}

import sys

def solve():
    try:
        s = sys.stdin.readline().strip()
        if not s:
            print("")
            return

        result = []
        n = len(s)
        i = 0
        while i < n:
            current_char = s[i]
            count = 0
            j = i
            while j < n and s[j] == current_char:
                count += 1
                j += 1
            
            if count > 1:
                result.append(str(count - 1))
                result.append(current_char)
            else:
                result.append(current_char)
            
            i = j
        
        print("".join(result))

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：字符串、双指针
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是输入字符串的长度。每个字符被外层指针 i 和内层指针 j 各访问一次。
空间复杂度： $\mathcal{O}(N)$ 。在最坏的情况下（例如，字符串中没有连续重复的字符），压缩后的字符串长度与原字符串相同，需要 N 的空间来存储结果。