首页 > 试题广场 >

压缩算法

[编程题]压缩算法
  • 热度指数:5840 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小Q想要给他的朋友发送一个神秘字符串,但是他发现字符串的过于长了,于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩,对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100),例如字符串ABCABCABC将会被压缩为[3|ABC],现在小Q的同学收到了小Q发送过来的字符串,你能帮助他进行解压缩么? 



示例1

输入

"HG[3|B[2|CA]]F"

输出

"HGBCACABCACABCACAF"

说明

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

备注:
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;
python + 正则
import re
class Solution:
    def compress(self , s ):
        # write code here
        while re.findall(r'\[(\d+)\|([a-zA-Z]+)\]',s):
            s = re.sub(r'\[(\d+)\|([a-zA-Z]+)\]',lambda match:match.group(2)*int(match.group(1)),s)
        return s

发表于 2021-07-15 20:29:13 回复(1)
# 构造一个链表就好做了,用的是python,希望能帮助需要的同学
class Solution:
    class StackNode:
        def __init__(self, number=0, stack=None, last_node=None):
            self.number = number
            self.stack = stack
            self.last_node = last_node

    def compress(self, string):
        c, ans, number = '', '', 0
        current_node = self.StackNode(stack=[])
        for c in string:
            if c == '[':
                new_node = self.StackNode(stack=[], last_node=current_node)
                current_node = new_node
            elif '0' <= c <= '9':
                current_node.number = current_node.number * 10 + int(c)
            elif c == ']':
                current_node.last_node.stack += (current_node.number * current_node.stack)
                current_node = current_node.last_node
            elif 'A' <= c <= 'Z':
                current_node.stack.append(c)
        ans = ''
        for e in current_node.stack:
            ans += e
        return ans
发表于 2021-03-30 10:45:13 回复(2)