pythontip 100days-day4

Code › python
, ,

题目

将输入字符串str,例如’HHHEELLLOOOO’，压缩为’H3E2L3O4’。

例子

  • None -> None
  • ‘’ -> ‘’
  • ‘ABBC’ -> ‘AB2C’

假设

  1. 字符串字符仅由ascii字符组成
  2. 大小写敏感

tips

1.寻找连续出现的字符，并计算出现次数

答案

解法1：

class CompressString(object):

    def compress(self, string):
        if string is None or not string:
            return string
        result = ''
        prev_char = string[0]
        count = 0
        for char in string:
            if char == prev_char:
                count += 1
            else:
                result += self._calc_partial_result(prev_char, count)
                prev_char = char
                count = 1
        result += self._calc_partial_result(prev_char, count)
        return result
        
    def _calc_partial_result(self, prev_char, count):
        return prev_char + (str(count) if count > 1 else '')

性能：

  1. 时间复杂度O(n)
  2. 空间复杂度O(n)

关键点：

  1. 统计连续出现字符的次数
  2. 当前字符与上一字符不相同时，对上一字符进行压缩