【重点!!!】【栈】394.字符串解码

本文介绍了一种使用栈实现的解码字符串方法,针对包含嵌套括号和数字的编码,通过维护两个栈来解析并还原原始字符串。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

题目

法1:基于栈

重点是理解该题思路!!!
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Python

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                multi = 0
                res = ''
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = 10 * multi + int(c) 
            else:
                res += c

        return res

注意:关于python的一些语法知识
关键点分析:
(1)列表存储的是引用:
当执行stack.append([multi, res])时,列表[multi, res]会被添加到栈中。
列表中存储的是multi和res的当前值的引用(即指向这两个对象的指针)。
(2)不可变类型的特性:
multi是整数(不可变类型),res是字符串(同样不可变)。
不可变对象一旦创建,其值无法被修改,只能被重新赋值(即变量指向新的对象)。
(3)代码逻辑的安全性:
在遇到[时,multi和res的当前值被保存到栈中。
随后,multi被重置为0,res被重置为空字符串’'。
在遇到]时,从栈中弹出的是之前保存的原始值(因为整数和字符串不可变,原始值未被修改)。

Java

class Solution {
    public String decodeString(String s) {
        int multi = 0, i = 0;
        StringBuilder res = new StringBuilder();
        LinkedList<Integer> multiStack = new LinkedList<>();
        LinkedList<String> stringStack = new LinkedList<>();
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == '[') {
                multiStack.offerLast(multi);
                stringStack.offerLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmpBuilder = new StringBuilder();
                int tmpMulti = multiStack.removeLast();
                for (int j = 0; j < tmpMulti; ++j) {
                    tmpBuilder.append(res);
                }
                res = new StringBuilder(stringStack.removeLast() + tmpBuilder.toString());
            } else if (c >= '0' && c <= '9') {
                multi = 10 * multi + c - '0';
            } else {
                res.append(c);
            }
            ++i;
        }

        return res.toString();
    }
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值