当前位置：首页 > article >正文

leetcode hot100【LeetCode 394.字符串解码】java实现

article 2025/1/24 19:33:27

LeetCode 394.字符串解码

题目描述

给定一个经过编码的字符串，编码规则为 k[encoded_string]，其中 encoded_string 中的每个字符都会重复 k 次。编写一个函数来解码这个字符串。

示例 1：

输入：s = "3[a]2[bc]", 返回 "aaabcbc".

示例 2：

输入："3[a2[c]]", 返回 "accaccacc".

示例 3：

"2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

示例 4：

"abc3[cd]xyz", 返回 "abccdcdcdxyz".

Java 实现代码

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> resultStack = new Stack<>();
        StringBuilder current = new StringBuilder();
        int k = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                // 处理连续数字
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                // 遇到 '['，将当前结果和倍数压栈
                countStack.push(k);
                resultStack.push(current);
                // 重置 k 和 current
                k = 0;
                current = new StringBuilder();
            } else if (ch == ']') {
                // 遇到 ']'，从栈中弹出倍数和之前的字符串
                int repeatTimes = countStack.pop();
                StringBuilder decoded = resultStack.pop();
                // 将当前字符串重复 repeatTimes 次后附加回去
                for (int i = 0; i < repeatTimes; i++) {
                    decoded.append(current);
                }
                current = decoded;
            } else {
                // 处理普通字符
                current.append(ch);
            }
        }
        return current.toString();
    }
}

解题思路

这个问题可以通过使用栈来解决。我们遍历字符串，使用一个栈来存储中间结果，以及一个计数器来记录数字。当遇到 [ 时，我们将当前的字符串和数字压入栈中，并重置计数器和当前字符串。当遇到 ] 时，我们从栈中弹出数字和之前的字符串，并将当前字符串重复相应的次数，并与之前的字符串拼接。最后，返回栈顶的字符串。