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),在最坏的情况下,我们可能需要将整个字符串存储在栈中。