Medium

题目描述

给你一个字符串 word，请你使用以下算法对其进行压缩：

从空字符串 comp 开始。当 word 不为空 时，执行以下操作：

  • 移除 word 的最长前缀，该前缀由单一字符 c 重复构成，且 c 最多重复 9 次。
  • 将前缀的长度和字符 c 追加到 comp。

返回字符串 comp。

示例 1：

输入：word = "abcde"
输出："1a1b1c1d1e"
解释：
初始时，comp = ""。执行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。
对于每个前缀，将 "1" 和对应字符追加到 comp。

示例 2：

输入：word = "aaaaaaaaaaaaaabb"
输出："9a5a2b"
解释：
初始时，comp = ""。执行 3 次操作，分别选择 "aaaaaaaaa"、"aaaaa" 和 "bb" 作为前缀。
- 对于前缀 "aaaaaaaaa"，将 "9a" 追加到 comp。
- 对于前缀 "aaaaa"，将 "5a" 追加到 comp。
- 对于前缀 "bb"，将 "2b" 追加到 comp。

提示：

  • 1 <= word.length <= 2 * 10^5
  • word 仅由小写英文字母组成。

解题思路

解题思路

这是一个字符串压缩问题，关键是理解压缩规则：每次取最多9个连续相同字符作为前缀进行压缩。

算法分析

  1. 贪心策略：每次尽可能取更多的相同字符（最多9个），这样能得到更好的压缩效果。

  2. 双指针遍历：

    • 使用一个指针 i 遍历字符串
    • 对于每个位置，统计从当前位置开始有多少个连续相同字符
    • 取最多9个字符作为一组进行压缩

  3. 具体步骤：

    • 从字符串开头开始，记录当前字符
    • 统计连续相同字符的个数，但不超过9个
    • 将个数和字符拼接到结果字符串中
    • 继续处理下一组字符

时间复杂度优化

虽然看起来是嵌套循环，但内层循环最多执行9次，所以整体时间复杂度仍然是 O(n)。每个字符只被访问一次。

这种方法简单直观，代码实现清晰，是最优解法。

代码实现

class Solution {
public:
    string compressedString(string word) {
        string comp = "";
        int i = 0;
        int n = word.length();
        
        while (i < n) {
            char c = word[i];
            int count = 0;
            
            // 统计连续相同字符个数，最多9个
            while (i < n && word[i] == c && count < 9) {
                count++;
                i++;
            }
            
            // 将个数和字符追加到结果中
            comp += to_string(count) + c;
        }
        
        return comp;
    }
};

class Solution:
    def compressedString(self, word: str) -> str:
        comp = ""
        i = 0
        n = len(word)
        
        while i < n:
            c = word[i]
            count = 0
            
            # 统计连续相同字符个数，最多9个
            while i < n and word[i] == c and count < 9:
                count += 1
                i += 1
            
            # 将个数和字符追加到结果中
            comp += str(count) + c
        
        return comp

public class Solution {
    public string CompressedString(string word) {
        StringBuilder comp = new StringBuilder();
        int i = 0;
        int n = word.Length;
        
        while (i < n) {
            char c = word[i];
            int count = 0;
            
            // 统计连续相同字符个数，最多9个
            while (i < n && word[i] == c && count < 9) {
                count++;
                i++;
            }
            
            // 将个数和字符追加到结果中
            comp.Append(count.ToString()).Append(c);
        }
        
        return comp.ToString();
    }
}

/**
 * @param {string} word
 * @return {string}
 */
var compressedString = function(word) {
    let comp = "";
    let i = 0;
    const n = word.length;
    
    while (i < n) {
        const c = word[i];
        let count = 0;
        
        // 统计连续相同字符个数，最多9个
        while (i < n && word[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)每个字符最多被访问一次，内层循环最多9次
空间复杂度O(1)除了结果字符串外，只使用常数额外空间

相关题目