Python递归实现字符串的压缩与解压缩算法

2023-04-16 00:00:00 字符串 递归 解压缩

字符串压缩算法:

def compress_str(s):
    if len(s) == 0:
        return ''
    elif len(s) == 1:
        return s + '1'
    else:
        count = 1
        compressed_str = ''
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                compressed_str += s[i-1] + str(count)
                count = 1
        compressed_str += s[i] + str(count)
        return compressed_str

这个算法的思想是遍历字符串,如果当前字符与上一个字符相等,计数器加1,如果不相等,则将上一个字符及其出现次数拼接到压缩字符串的末尾。最后一个字符也要拼接上。

例如,对字符串“pidancode.com”进行压缩,返回结果为“p1i1d1a1n1c1o2d1e1.1c1o1m1”。其中“1”代表出现次数。

字符串解压缩算法:

def decompress_str(s):
    if len(s) == 0:
        return ''
    else:
        decompressed_str = ''
        i = 0
        while i < len(s):
            c = s[i]
            count = 0
            i += 1
            while i < len(s) and s[i].isdigit():
                count = count * 10 + int(s[i])
                i += 1
            decompressed_str += c * count
        return decompressed_str

这个算法的思想是遍历字符串,如果当前字符是字母,则将其加入解压缩字符串的末尾,如果是数字,则将数字解析出来,并将其前面的字母重复加入解压缩字符串的末尾相应的次数。

例如,对压缩字符串“p1i1d1a1n1c1o2d1e1.1c1o1m1”进行解压缩,返回结果为“pidancode.com”。

相关文章