【Leetcode Daily】394字符串解码

发表于2025-08-27|更新于2025-08-27|力扣日常 | LeetcodeDaily

|总字数:463|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个字符串，对于其中 3[*] 的部分，就替换成 *** 这样把中括号内部重复 3 遍，前面的数字部分可以为 1-300 的任意整数。

思路分享

一开始的思路是对于[]的内部直接延长为数字倍数，但发现这个思路不太好应对多层嵌套。
于是，如果用栈记录每层的字符情况以及要乘的数字倍数情况，然后在括号结束时计算倍数，就可以解决嵌套的问题。
不过这里记录一个 Python 有趣的知识，对于 l = ["1", "2"] 这样的列表，用 l[-1] += l.pop() 的结果是什么呢？这个代码的原本目标是去除最后的一个元素，并将内容与前一个字符串融合，即目标答案是 [“12”]。但实际上却是 [“22”]。原因是虽然表达式是右到左来解析，但左边的 l[-1] 的“值”在式子一开始就是固定的，十分微妙，不知道算 bug 还是什么。（3.12.2）只能说各位实际上写的时候，尽量避免 -1 和 pop 这种比较相关的操作同时运行。
灵神的题解一如既往的神啊，参考题解与灵神的栈思路类似

https://leetcode.cn/problems/decode-string/solutions/3744428/di-gui-yong-zhan-mo-ni-di-gui-pythonjava-kcsv/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def decodeString(self, s: str) -> str:
        count_rec = list()
        left_rec = list()
        contents = [""]
        count = 0
        for i, x in enumerate(s):
            if x == '[':
                count_rec.append(count)
                # left_rec.append(i)
                count = 0
                contents.append("")
            elif x == ']':
                tmp = contents.pop() * count_rec.pop()
                contents[-1] += tmp
            elif x.isdigit():
                count *= 10
                count += int(x)
            else:
                contents[-1] += x
            # print(contents)
            # print(count_rec)
            # print()
        # print(contents)
        return contents[0]

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/44bd772.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

相关推荐

【Leetcode Daily】844比较含退格的字符串

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个字符串，串中的 ‘#’ 被当作退格符，要求处理完退格符后，判断两个字符串是否相等。思路分享只要维护两个栈，在推入时 push（append），弹出时 pop 即可。重点是学习 Python 是如何模拟栈的，在 C++ 中有对应的 stl，就算不用标准 stack，也能用 vector 模拟。Python 中是先用 list 的 append 和 pop 方法，最后运用 join 把 list 里面的各个元素粘合起来。 "".join(stack)的意思就是以 "" 内容作为连接符（这里就是没有任何内容），把 stack 的元素连成字符串。代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def backspaceCompare(self, s: str, t: str) -> bool: def backspace(s: str): stack =...

【Leetcode Daily】1441用栈操作构建数组

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个 target 数组，现在会让数字从 1 到 n 输入，每次输入都算 Push 操作，而可以选择 Pop 弹出栈顶。求得到 target 数组的操作序列。思路分享正如题目所说，每次输入数字就算一次 Push，但是由于输入数字可能会跨越一定数值，因此需要计算中间需要多少次 Push 和对应的 Pop。对于需要 Pop 的处理有大致两种方法，一种是每 Push 一个就马上 Pop，另一种是 Push 完中间的再一次性 Pop，下面选用第一种方法。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314class Solution: def buildArray(self, target: List[int], n: int) -> List[str]: ans = [] index = 1 for x in target: while index < x: ...

【Leetcode Daily】682棒球比赛

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个列表，这个列表有数字或者特殊符号，要求按顺序遍历列表计数，遇到特殊符号则按规则运算（取前两数之和，取上一数两倍，去掉上一数），求最终数值和。思路分享就是简单的模拟一个栈，遇到数字直接 append 进去，遇到符号就取数运算把结果 append 进去，或者把最后一个数字 pop 出来。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314class Solution: def calPoints(self, operations: List[str]) -> int: rec = list() for i in operations: if i == "+": rec.append(rec[-1]+rec[-2]) elif i == "D": rec.append(rec[-1]*2) ...

【Leetcode Daily】2390从字符串中移除星号

题目浅析想查看原题可以点击题目链接。简单地说，就是把字符串中的星号当作退格，每次遇到就删除前面一个字符，求最终处理后的字符串。思路分享除了符号不同，与题目【Leetcode Daily】844比较含退格的字符串几乎一摸一样，故不赘述。代码解答（强烈建议自行解答后再看）参考题解 12345678910class Solution: def removeStars(self, s: str) -> str: rec = list() for c in s: if c != '*': rec.append(c) elif rec: rec.pop() return "".join(rec)

【Leetcode Daily】1472设计浏览器历史记录

题目浅析想查看原题可以点击题目链接。简单地说，就是设计一个类，能模拟浏览器的访问，返回，前进的三个功能。思路分享两个思路，一个是用两个栈来处理前进和返回两个功能的地址，访问和前进的时候把地址存返回的栈，返回的时候把地址存前进。另一个是只用一个栈，这个栈存储访问地址的记录，根据前进和返回的需要，直接访问对应下标（其实已经不算是栈了吧，毕竟指针跳来跳去的） https://leetcode.cn/problems/design-browser-history/solutions/3072257/zhan-mo-ni-pythonjavaccgojsrust-by-endle-g8bn/ 无论是从实现的难易程度还是程序的效率，都是第二种思路更为优秀。不过一般初见本题都会想第一个思路~ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class...

【Leetcode Daily】946验证栈序列

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个序列，分别是往栈 push 内容的顺序，另一个是可能的从栈 pop 的顺序，需要验证这个 pop 的顺序是否合理（可能存在）。思路分享只要通过列表，模拟栈的推入，一旦栈的顶部与弹出序列的首个相同，就执行弹出的操作即可。这样的思路下，最终只要验证是否把弹出序列用完就行。虽然下面的参考题解算是解决了问题，但是这个连接通过 list 的 pop 操作，能够更加优美地解决问题，值得借鉴。 https://leetcode.cn/problems/validate-stack-sequences/solutions/2362056/946-yan-zheng-zhan-xu-lie-mo-ni-qing-xi-wpxi6/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) ->...

数据加载中