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

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 和 currentk = 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();}
}

解题思路

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

复杂度分析

• 时间复杂度：O(N)，其中 N 是字符串 s 的长度。因为我们需要遍历字符串中的每个字符。
• 空间复杂度：O(N)，在最坏的情况下，我们可能需要将整个字符串存储在栈中。