LeetCode 443. 压缩字符串

Categories:

题目描述
思路分析
1. 解法一：双指针原地压缩（推荐）
2. 解法二：分组循环
相似题目

题目描述

✅ 443. 压缩字符串

思路分析

解法一：双指针原地压缩（推荐）

核心思路：

使用 read 指针从左到右扫描字符数组，统计当前连续字符的数量。

使用 write 指针记录压缩结果写入的位置（原地修改）。

每统计完一段连续字符后，先写入字符本身，若计数大于 1，再将计数逐位拆分写入（十位、百位等均需单独写入对应数字字符）。

最终返回 write 指针的值，即压缩后数组的新长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符数组的长度，每个字符最多被读取和写入一次。

空间复杂度：O(1)，原地修改，只使用常数额外空间。

class Solution {
    public int compress(char[] chars) {
        // write 指针记录写入位置，read 指针扫描原数组
        int write = 0;
        int read = 0;
        int n = chars.length;

        while (read < n) {
            char cur = chars[read];
            int count = 0;

            // 统计当前连续字符的数量
            while (read < n && chars[read] == cur) {
                read++;
                count++;
            }

            // 写入字符本身
            chars[write++] = cur;

            // 计数大于 1 时，逐位写入数字字符
            if (count > 1) {
                String countStr = String.valueOf(count);
                for (char c : countStr.toCharArray()) {
                    chars[write++] = c;
                }
            }
        }

        return write;
    }
}

func compress(chars []byte) int {
    // write 指针记录写入位置，read 指针扫描原数组
    write := 0
    read := 0
    n := len(chars)

    for read < n {
        cur := chars[read]
        count := 0

        // 统计当前连续字符的数量
        for read < n && chars[read] == cur {
            read++
            count++
        }

        // 写入字符本身
        chars[write] = cur
        write++

        // 计数大于 1 时，逐位写入数字字符
        if count > 1 {
            countStr := strconv.Itoa(count)
            for i := 0; i < len(countStr); i++ {
                chars[write] = countStr[i]
                write++
            }
        }
    }

    return write
}

解法二：分组循环

核心思路：

将字符数组按连续相同字符分组，每组记录起始位置和结束位置。

分组边界处理：i 从 0 出发，j 向右扫描直到遇到不同字符，[i, j) 即为一组。

每组处理完后令 i = j，继续下一组，这是分组循环的标准写法，可避免边界遗漏。

计数写入时同样需要逐位拆分。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符数组的长度，每个字符恰好被访问一次。

空间复杂度：O(1)，原地修改，只使用常数额外空间。

class Solution {
    public int compress(char[] chars) {
        int write = 0;
        int n = chars.length;
        int i = 0;

        while (i < n) {
            char cur = chars[i];
            // j 向右扫描，直到遇到不同字符，[i, j) 为一组
            int j = i;
            while (j < n && chars[j] == cur) {
                j++;
            }
            int count = j - i;

            // 写入字符
            chars[write++] = cur;

            // 计数大于 1 时，逐位写入数字字符
            if (count > 1) {
                String countStr = String.valueOf(count);
                for (char c : countStr.toCharArray()) {
                    chars[write++] = c;
                }
            }

            // 移动到下一组起始位置
            i = j;
        }

        return write;
    }
}

func compress(chars []byte) int {
    write := 0
    n := len(chars)
    i := 0

    for i < n {
        cur := chars[i]
        // j 向右扫描，直到遇到不同字符，[i, j) 为一组
        j := i
        for j < n && chars[j] == cur {
            j++
        }
        count := j - i

        // 写入字符
        chars[write] = cur
        write++

        // 计数大于 1 时，逐位写入数字字符
        if count > 1 {
            countStr := strconv.Itoa(count)
            for k := 0; k < len(countStr); k++ {
                chars[write] = countStr[k]
                write++
            }
        }

        // 移动到下一组起始位置
        i = j
    }

    return write
}

相似题目

题目	难度	考察点
38. 外观数列	中等	字符串、模拟
271. 字符串的编码与解码	中等	字符串、设计
344. 反转字符串	简单	双指针、字符串
345. 反转字符串中的元音字母	简单	双指针、字符串
459. 重复的子字符串	简单	字符串、KMP
604. 迭代压缩字符串	简单	字符串、设计
1313. 解压缩编码列表	简单	数组、模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/44507116