LeetCode 394. 字符串解码

Categories:

Tags:

题目描述
思路分析
1. 解法一：栈（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 394. 字符串解码

思路分析

解法一：栈（推荐）

核心思路：

字符串中存在嵌套结构（如 3[a2[c]]），天然适合用栈处理括号嵌套。

维护两个栈：numStack（重复次数）和 strStack（外层字符串片段），以及当前正在构建的字符串 curStr 和当前数字 num。

逐字符扫描，按字符类型分四种情况处理：

数字：累积到 num（支持多位数，如 12[a]）。

[：将 curStr 和 num 分别压入对应栈，重置 curStr = ""、num = 0，进入新一层嵌套。

]：弹出栈顶的重复次数 k 和上层字符串 prevStr，将 curStr 重复 k 次后拼接到 prevStr，更新 curStr，回到上一层。

字母：直接追加到 curStr。

示例 3[a2[c]] 的处理过程：

遇到 [：num=3, curStr="" 入栈，curStr="a" 继续累积

遇到内层 [：num=2, curStr="a" 入栈，curStr="c" 继续累积

遇到 ]：弹出 2, "a"，curStr = "a" + "cc" = "acc"

遇到 ]：弹出 3, ""，curStr = "" + "accaccacc" = "accaccacc"

复杂度分析：

时间复杂度：O(n × maxK)，其中 n 为字符串长度，maxK 为最大重复次数

空间复杂度：O(n)，栈的空间

class Solution {
    public String decodeString(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<StringBuilder> strStack = new ArrayDeque<>();
        StringBuilder curStr = new StringBuilder();
        int curNum = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // 处理多位数字
                curNum = curNum * 10 + (c - '0');
            } else if (c == '[') {
                // 进入新一层嵌套，将当前状态压栈并重置
                numStack.push(curNum);
                strStack.push(curStr);
                curStr = new StringBuilder();
                curNum = 0;
            } else if (c == ']') {
                // 退出当前层，弹出重复次数和上层字符串，拼接结果
                int count = numStack.pop();
                StringBuilder pre = strStack.pop();
                for (int i = 0; i < count; i++) {
                    pre.append(curStr);
                }
                curStr = pre;
            } else {
                // 普通字母直接追加
                curStr.append(c);
            }
        }
        return curStr.toString();
    }
}

func decodeString(s string) string {
	numStack := make([]int, 0)
	strStack := make([]string, 0)
	curStr := ""
	num := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= '0' && c <= '9' {
			// 处理多位数字
			num = num*10 + int(c-'0')
		} else if c == '[' {
			// 进入新一层嵌套，将当前状态压栈并重置
			numStack = append(numStack, num)
			strStack = append(strStack, curStr)
			curStr, num = "", 0
		} else if c == ']' {
			// 退出当前层，弹出重复次数和上层字符串，拼接结果
			count := numStack[len(numStack)-1]
			numStack = numStack[:len(numStack)-1]
			preStr := strStack[len(strStack)-1]
			strStack = strStack[:len(strStack)-1]
			curStr = preStr + strings.Repeat(curStr, count)
		} else {
			// 普通字母直接追加
			curStr += string(c)
		}
	}
	return curStr
}

解法二：递归

核心思路：

将字符串解码看作递归子问题：遇到 [ 时递归处理括号内的子串，返回解码结果后继续拼接。

使用一个全局下标 idx 指向当前处理位置，递归函数负责处理当前层的内容，遇到 ] 时返回。

递归过程：

遇到数字：累积重复次数 k。

遇到 [：递归调用，获取括号内解码结果，将其重复 k 次后拼接到当前层。

遇到字母：追加到当前层结果。

遇到 ] 或到达末尾：返回当前层结果。

复杂度分析：

时间复杂度：O(n × maxK)，其中 n 为字符串长度，maxK 为最大重复次数

空间复杂度：O(n)，递归调用栈的深度

class Solution {
    private int idx = 0;

    public String decodeString(String s) {
        return decode(s);
    }

    private String decode(String s) {
        StringBuilder result = new StringBuilder();
        int num = 0;
        while (idx < s.length()) {
            char c = s.charAt(idx);
            if (Character.isDigit(c)) {
                // 累积重复次数（支持多位数）
                num = num * 10 + (c - '0');
                idx++;
            } else if (c == '[') {
                // 递归处理括号内的子串
                idx++;
                String inner = decode(s);
                for (int i = 0; i < num; i++) {
                    result.append(inner);
                }
                num = 0;
            } else if (c == ']') {
                // 当前层结束，返回结果
                idx++;
                return result.toString();
            } else {
                // 普通字母直接追加
                result.append(c);
                idx++;
            }
        }
        return result.toString();
    }
}

func decodeString(s string) string {
	idx := 0
	var decode func() string
	decode = func() string {
		result := ""
		num := 0
		for idx < len(s) {
			c := s[idx]
			if c >= '0' && c <= '9' {
				// 累积重复次数（支持多位数）
				num = num*10 + int(c-'0')
				idx++
			} else if c == '[' {
				// 递归处理括号内的子串
				idx++
				inner := decode()
				result += strings.Repeat(inner, num)
				num = 0
			} else if c == ']' {
				// 当前层结束，返回结果
				idx++
				return result
			} else {
				// 普通字母直接追加
				result += string(c)
				idx++
			}
		}
		return result
	}
	return decode()
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈匹配括号
224. 基本计算器	困难	栈模拟表达式求值
227. 基本计算器 II	中等	栈模拟表达式求值
385. 迷你语法分析器	中等	栈、递归解析嵌套结构
726. 原子的数量	困难	栈解析嵌套字符串
1106. 解析布尔表达式	困难	栈、递归解析
471. 编码最短长度的字符串	困难	动态规划、字符串编码

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/48855635