当前位置：首页>python>Python题库第3题:3[a2[c]]字符串解码

Python题库第3题:3[a2[c]]字符串解码

2026-07-01 19:58:17

Python，速成心法

敲代码，查资料，问Ai

练习，探索，总结，优化

★★★★★博文创作不易，源码代码的过程中，如有疑问的地方，欢迎大家指正留言交流。喜欢的老铁可以多多点赞+收藏分享+置顶，小红牛在此表示感谢。★★★★★

Python打包教程07：还不会用--add-data参数，添加资源文件吗？

Python打包教程04：UPX安装与使用（减小.exe体积）

Python打包教程03：PyInstaller命令使用指南

Python教程：PyCharm安装过程中遇到的中英文对照表

和Python编程相关的，中英文对照词汇表

2025年Python和pycharm安装下载教程

Python零基础教程：小白入门自学知识点大纲

Python教程：找到字符串中最长回文子串（上海自来水来自海上）

Python题库第2题：找出三数之和为零的数据

1.字符串解码（中等难度）题目描述：给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为：k[encoded_string]，表示 encoded_string 重复 k 次。k 保证为正整数。

你可以认为输入字符串总是有效的；没有额外的空格，方括号总是匹配的，且 k 和 encoded_string 符合规范。

另外，编码中可能存在嵌套，例如 "3[a2[c]]"。

# 示例输入: "3[a]2[bc]"输出: "aaabcbc"输入: "3[a2[c]]"输出: "accaccacc"输入: "2[abc]3[cd]ef"输出: "abcabccdcdcdef"输入: "abc3[cd]xyz"输出: "abccdcdcdxyz"

2.要求：时间复杂度 O(n)，n 为解码后字符串长度（或原始编码字符串长度）。可使用栈来解决，不能使用 eval 或正则表达式。

3.解题思路说明：

a.栈结构：栈中每个元素是一个元组 (之前已解码的字符串, 当前括号前的重复次数)。

b.遍历字符：

数字：可能有多位（如 100），累乘加当前数字得到完整整数。

[：将当前累积的字符串和数字压入栈，然后重置当前字符串和数字，开始处理括号内的内容。]：弹出栈顶 (prev_str, repeat)，将当前字符串重复 repeat 次后，拼接到 prev_str 后面，作为新的当前字符串。

字母：直接追加到当前字符串。

c.最终返回：遍历结束后，current_str 即为完整解码字符串。

d.复杂度：每个字符最多入栈出栈一次，时间复杂度 O(n)，空间复杂度 O(n)（栈深度）。

该解法是解决字符串解码问题的标准方法，清晰且高效。

↓ 完整源码如下 ↓

# -*- coding: utf-8 -*-# @Author : 小红牛# 微信公众号：wdPythondef decode_string(s: str) -> str:    """    解码字符串。    参数:        s: 编码字符串    返回:        str: 解码后的字符串    """    stack = []          # 用于存储 (之前的字符串, 重复次数)    current_str = ""    # 当前正在构建的字符串    current_num = 0     # 当前的重复次数    for ch in s:        if ch.isdigit():            # 处理多位数字            current_num = current_num * 10 + int(ch)        elif ch == '[':            # 遇到 '['，将当前状态压栈，并重置            stack.append((current_str, current_num))            current_str = ""            current_num = 0        elif ch == ']':            # 弹出栈顶，重复当前字符串            prev_str, repeat = stack.pop()            current_str = prev_str + current_str * repeat        else:            # 普通字母，直接追加            current_str += ch    return current_str# 测试用例if __name__ == "__main__":    print(decode_string("3[a]2[bc]"))      # "aaabcbc"    print(decode_string("3[a2[c]]"))       # "accaccacc"    print(decode_string("2[abc]3[cd]ef"))  # "abcabccdcdcdef"    print(decode_string("abc3[cd]xyz"))    # "abccdcdcdxyz"    print(decode_string("100[leetcode]"))  # "leetcode"重复100次（测试大数字）    print(decode_string(""))               # ""