大厂面试真题详解:字符串解码-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:字符串解码

简介: 大厂面试真题详解:字符串解码

给出一个表达式 s,此表达式包括数字,字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式),请将这个表达式展开成一个字符串。

在线评测地址:领扣题库官网

样例1

输入: S = abc3[a]
输出: "abcaaa"

样例2

输入: S = 3[2[ad]3[pf]]xyz
输出: "adadpfpfpfadadpfpfpfadadpfpfpfxyz"

题解

把所有字符一个个放到 stack 里, 如果碰到了 ],就从 stack 找到对应的字符串和重复次数,decode 之后再放回 stack 里。

class Solution:
    """
    @param s: an expression includes numbers, letters and brackets
    @return: a string
    """
    def expressionExpand(self, s):
        stack = []
        for c in s:
            if c != ']':
                stack.append(c)
                continue
                
            strs = []
            while stack and stack[-1] != '[':
                strs.append(stack.pop())
            
            # skip '['
            stack.pop()
            
            repeats = 0
            base = 1
            while stack and stack[-1].isdigit():
                repeats += (ord(stack.pop()) - ord('0')) * base
                base *= 10
            stack.append(''.join(reversed(strs)) * repeats)
        
        return ''.join(stack)

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接