LeetCode解码字符串：Python转Java实现遇错求正确方案

问题描述 #

给定一个编码字符串，返回其解码后的字符串。编码规则为：k[encoded_string]，方括号内的encoded_string需被重复恰好k次，k为正整数。
输入字符串始终有效：无多余空格，方括号格式正确；原始数据不含数字，数字仅用于表示重复次数k，不会出现3a或2[4]这类输入。测试用例保证输出长度不超过10^5。

示例1：
输入: s = "3[a]2[bc]"
输出: "aaabcbc"

示例2：
输入: s = "3[a2[c]]"
输出: "accaccacc"

Python参考实现 #

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for char in s:
            if char != "]":
                stack.append(char)
            else:
                sub_str = ""
                while stack[-1] != "[":
                    sub_str = stack.pop() + sub_str
                stack.pop()
                multiplier = ""
                while stack and stack[-1].isdigit():
                    multiplier = stack.pop() + multiplier
                stack.append(int(multiplier) * sub_str)
        return "".join(stack)

问题Java代码分析与修正 #

原代码存在的问题 #

1. 栈操作逻辑错误：Python中stack.pop()是弹出栈顶元素（列表最后一个），但Java的ArrayDeque.pop()是弹出队列头部元素，导致取到的元素顺序完全错误。
2. 重复字符串添加低效且逻辑偏差：原代码通过循环多次添加subword到栈中，既低效又不符合Python中直接将重复后的完整字符串入栈的逻辑。
3. 数字判断方式冗余：使用Double.parseDouble捕获异常的方式判断数字，对于单个字符的数字来说过于冗余，且性能较差。

修正后的Java代码 #

class Solution {
    public String decodeString(String s) {
        Deque<String> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            if (c != ']') {
                stack.addLast(String.valueOf(c));
            } else {
                // 提取方括号内的子字符串
                StringBuilder subStr = new StringBuilder();
                while (!stack.getLast().equals("[")) {
                    subStr.insert(0, stack.removeLast());
                }
                // 弹出左括号
                stack.removeLast();
                
                // 提取数字乘数
                StringBuilder multiplier = new StringBuilder();
                while (!stack.isEmpty() && Character.isDigit(stack.getLast().charAt(0))) {
                    multiplier.insert(0, stack.removeLast());
                }
                int k = Integer.parseInt(multiplier.toString());
                
                // 将重复后的字符串入栈
                stack.addLast(subStr.toString().repeat(k));
            }
        }
        
        // 拼接栈中所有元素得到结果
        StringBuilder result = new StringBuilder();
        for (String str : stack) {
            result.append(str);
        }
        return result.toString();
    }
}

修正点说明 #

1. 栈操作修正：使用addLast()添加元素到栈顶，removeLast()弹出栈顶元素，完全对齐Python的栈行为。
2. 字符串重复优化：使用String.repeat(k)直接生成重复后的完整字符串，一次性入栈，提升效率且逻辑更简洁。
3. 数字判断优化：使用Character.isDigit()直接判断字符是否为数字，避免异常捕获的开销。
4. 使用StringBuilder提升性能：在拼接子字符串和数字时使用StringBuilder，比直接字符串拼接更高效，尤其处理长字符串时优势明显。

内容的提问来源于stack exchange，提问作者mattsmith5