0443. 压缩字符串

0443. 压缩字符串 #

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

题目大意 #

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

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

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

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

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

说明

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

示例

1
2
3
输入    chars = ["a","a","b","b","c","c","c"]
输出    返回 6 输入数组的前 6 个字符应该是["a","2","b","2","c","3"]
解释    "aa""a2" 替代"bb""b2" 替代"ccc""c3" 替代

解题思路 #

思路 1:快慢指针 #

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

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

思路 1:快慢指针代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
本站总访问量  次  |  您是本站第  位访问者