leetcode
leetcode 2751 ~ 2800
字符串压缩

字符串压缩

难度:

标签:

题目描述

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Example 1:

Input: "aabcccccaaa"
Output: "a2b1c5a3"

Example 2:

Input: "abbccd"
Output: "abbccd"
Explanation: 
The compressed string is "a1b2c2d1", which is longer than the original string.

 

Note:

  1. 0 <= S.length <= 50000

代码结果

运行时间: 26 ms, 内存: 16.1 MB

/*
 * 思路：
 * 1. 使用Java Stream API处理字符串。
 * 2. 将字符串拆分为字符流，并使用Collectors.groupingBy统计每个字符的连续出现次数。
 * 3. 构建压缩后的字符串。
 * 4. 如果压缩后的字符串长度大于或等于原字符串长度，则返回原字符串。
 */

import java.util.stream.Collectors;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.IntStream;

public class StringCompressionStream {
    public String compress(String s) {
        if (s == null || s.length() == 0) return s;

        List<Character> chars = s.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
        StringBuilder compressed = new StringBuilder();

        IntStream.range(0, chars.size()).forEach(i -> {
            int count = 1;
            while (i + 1 < chars.size() && chars.get(i).equals(chars.get(i + 1))) {
                count++;
                i++;
            }
            compressed.append(chars.get(i)).append(count);
        });

        return compressed.length() >= s.length() ? s : compressed.toString();
    }

    public static void main(String[] args) {
        StringCompressionStream scs = new StringCompressionStream();
        System.out.println(scs.compress("aabcccccaaa"));  // 输出: a2b1c5a3
        System.out.println(scs.compress("abbccd"));      // 输出: abbccd
    }
}

解释

方法:

该题解通过遍历字符串S，并计算每个字符连续出现的次数来构造压缩后的字符串。遍历过程中，用ch_prev记录前一个字符，用count记录该字符的连续出现次数。为了简化末尾字符的处理，给字符串S额外添加了一个不同的字符'@'作为结束标记。这样，当遇到新字符或结束字符'@'时，将前一个字符及其计数追加到结果字符串ret中。最后比较压缩后字符串的长度与原字符串的长度，如果压缩后没有变短，则返回原字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在字符串'S'末尾添加'@'字符，这样做有什么特别的意义或优势？
▷
在字符串'S'末尾添加'@'字符主要是为了简化代码逻辑，确保可以正确处理原字符串中最后一个字符序列的压缩。由于压缩过程需要检测到字符变化时才记录前一个字符的出现次数，如果不添加结束标记，循环结束时需要额外的逻辑来处理最后一组字符。添加一个不常见的字符如'@'作为结束标记，可以在循环中统一处理所有字符的结束，避免了在循环外单独处理最后一组字符的复杂性。
🦆
如果字符串S中包含了'@'字符，这种方法添加'@'作为结束标记还会有效吗？
▷
如果原始字符串'S'中已经包含了'@'字符，那么使用'@'作为结束标记将不再有效，因为算法会误认为字符串结束了，从而导致压缩结果错误。在这种情况下，需要选择一个保证不会出现在原字符串中的字符作为结束标记，或者需要改变方法，例如通过检查是否到达字符串的实际末尾来结束循环，而不依赖于特定的结束标记字符。
🦆
在比较压缩后的字符串长度和原字符串长度时，为什么选择在循环结束后比较，而不是在循环过程中就终止返回原字符串？
▷
在循环过程中终止并返回原字符串的做法可能听起来可以提前结束处理，节省时间。但是，由于无法预先知道压缩的结果长度（因为字符序列的长度和分布未知），只有在完全构建完压缩后的字符串后，才能准确知道其长度。因此，必须等到循环完成后，才能进行长度比较，并决定是否返回压缩字符串或原字符串。这样可以保证压缩逻辑的正确性和完整性。

相关问题

URL化字符串轮转