LeetCode 394解码字符串：两种栈解法差异及错误原因问询

我的低效解法 #

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        for ch in s:
            if ch != ']':
                stack.append(ch)
            else:
                new_s = ''
                while stack[-1] != '[':
                    new_s += stack.pop()
                new_s = new_s[::-1]
                stack.pop()

                number = ''
                while stack and stack[-1].isdigit():
                    print(stack[-1])
                    number += stack.pop()
                number = int(number[::-1])

                print(new_s)
                stack.append(number * new_s)
        
        return "".join(stack) 

正确解法 #

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        for ch in s:
            if ch != ']':
                stack.append(ch)
            else:
                # Collect the characters forming the encoded string
                decoded_string = []
                while stack[-1] != '[':
                    decoded_string.append(stack.pop())
                stack.pop()  # Remove the '['
                
                # Now reverse the decoded string to get the correct order
                decoded_string = ''.join(decoded_string[::-1])
                
                # Get the number (how many times to repeat)
                number = []
                while stack and stack[-1].isdigit():
                    number.append(stack.pop())
                number = int(''.join(number[::-1]))

                # Append the repeated decoded string back to the stack
                stack.append(number * decoded_string)
        
        return "".join(stack)

问题现象 #

输入3[z]2[2[y]pq4[2[jk]e1[f]]]ef时：

• 我的输出：zzzyypqfejkjkfejkjkfejkjkfejkjkyypqfejkjkfejkjkfejkjkfejkjkef
• 预期输出：zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkefef

核心差异原因 #

你误以为两者仅反转方式不同，但实际上收集待解码内容的逻辑完全不同，这才是错误的根源：

1. 正确解法的逻辑：

   • 用列表decoded_string收集栈中弹出的元素，保留每个元素的完整性——不管弹出的是单个字符（如'e'）还是已经解码好的长字符串（如'jkjk'），都作为独立元素存入列表。
   • 反转列表后，直接将所有元素按顺序拼接，得到的是原栈中元素从底到顶的正确顺序（比如栈中从底到顶是yy→p→q→jkjkef，反转列表后拼接为yypqjkjkef）。

2. 你的解法的逻辑：

   • 用字符串new_s累加栈中弹出的元素，会破坏已解码字符串的完整性——弹出的长字符串（如'jkjk'）会被拆成单个字符拼接到new_s中。
   • 反转整个字符串时，是把所有字符的顺序完全颠倒，而不是保留原元素的顺序反转。比如栈中从底到顶是yy→p→q→jkjkef，弹出后new_s是jkjkefqpyy，反转整个字符串得到yyqpfejkjk，这就完全打乱了原有的结构。

举个具体的例子：
当处理外层2[2[y]pq4[...]]的]时，栈中元素从顶到底是jkjkef*4→q→p→yy→[：

• 正确解法收集到的列表是['jkjkef*4', 'q', 'p', 'yy']，反转后拼接为yypqjkjkef*4，符合预期。
• 你的解法得到的new_s是jkjkef*4qpyy，反转后变成yyqpfejkjk*4，这就是输出中出现yypqfejkjk...的原因。

内容的提问来源于stack exchange，提问作者kirych.hevc