跳至主要內容

0443. 压缩字符串

ITCharge大约 3 分钟

0443. 压缩字符串open in new window

  • 标签:双指针、字符串
  • 难度:中等

题目链接

题目大意

描述:给定一个字符数组 charschars。请使用下述算法压缩:

从一个空字符串 ss 开始。对于 charschars 中的每组连续重复字符:

  • 如果这一组长度为 11,则将字符追加到 ss 中。
  • 如果这一组长度超过 11,则需要向 ss 追加字符,后跟这一组的长度。

压缩后得到的字符串 ss 不应该直接返回 ,需要转储到字符数组 charschars 中。需要注意的是,如果组长度为 10101010 以上,则在 charschars 数组中会被拆分为多个字符。

要求:在修改完输入数组后,返回该数组的新长度。

说明

  • 1chars.length20001 \le chars.length \le 2000
  • chars[i]chars[i] 可以是小写英文字母、大写英文字母、数字或符号。
  • 必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例

  • 示例 1:
输入:chars = ["a","a","b","b","c","c","c"]
输出:返回 6 ,输入数组的前 6 个字符应该是:["a","2","b","2","c","3"]
解释:"aa""a2" 替代。"bb""b2" 替代。"ccc""c3" 替代。
  • 示例 2:
输入:chars = ["a"]
输出:返回 1 ,输入数组的前 1 个字符应该是:["a"]
解释:唯一的组是“a”,它保持未压缩,因为它是一个字符。

解题思路

思路 1:快慢指针

题目要求原地修改字符串数组。我们可以使用快慢指针来解决原地修改问题,具体解决方法如下:

  • 定义两个快慢指针 slowslowfastfast。其中 slowslow 指向压缩后的当前字符位置,fastfast 指向压缩前的当前字符位置。
  • 记录下当前待压缩字符的起始位置 faststart=startfast\underline{}start = start,然后过滤掉连续相同的字符。
  • 将待压缩字符的起始位置的字符存入压缩后的当前字符位置,即 chars[slow]=chars[faststart]chars[slow] = chars[fast\underline{}start],并向右移动压缩后的当前字符位置,即 slow+=1slow += 1
  • 判断一下待压缩字符的数目是否大于 11
    • 如果数量为 11,则不用记录该数量。
    • 如果数量大于 11(即 fastfaststart>0fast - fast\underline{}start > 0),则我们需要将对应数量存入压缩后的当前字符位置。这时候还需要判断一下数量是否大于等于 1010
      • 如果数量大于等于 1010,则需要先将数字从个位到高位转为字符,存入压缩后的当前字符位置(此时数字为反,比如原数字是 321321,则此时存入后为 123123)。因为数字为反,所以我们需要将对应位置上的子字符串进行反转。
      • 如果数量小于 1010,则直接将数字存入压缩后的当前字符位置,无需取反。
  • 判断完之后向右移动压缩前的当前字符位置 fastfast,然后继续压缩字符串,直到全部压缩完,则返回压缩后的当前字符位置 slowslow 即为答案。

思路 1:代码

class Solution:
    
    def compress(self, chars: List[str]) -> int:
        def reverse(left, right):
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1

        slow, fast = 0, 0
        while fast < len(chars):
            fast_start = fast
            while fast + 1 < len(chars) and chars[fast + 1] == chars[fast]:
                fast += 1
            
            chars[slow] = chars[fast_start]
            slow += 1

            if fast - fast_start > 0:
                cnt = fast - fast_start + 1
                slow_start = slow
                while cnt != 0:
                    chars[slow] = str(cnt % 10)
                    slow += 1
                    cnt = cnt // 10
                reverse(slow_start, slow - 1)
            
            fast += 1
        return slow

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为字符串 ss 的长度。
  • 空间复杂度O(1)O(1)