LeetCode394——字符串解码

ゝ一纸荒年。 2022-01-26 15:01 192阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/decode-string/][https_leetcode-cn.com_problems_decode-string]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：栈、递归

### 思路一：利用栈这种数据结构 ###

从左到右遍历所给字符串：

当遇到右括号时，我们需要利用栈将与该右括号相匹配的左括号找出来，并将两括号间的内容重复相应的次数再入栈。

当遇到数字时，由于题目没有规定重复次数都是个位数，所以存在100次这样的情况，需要组合出该数字，再将该数字以字符串形式入栈。

对于其他字符，我们直接入栈即可。

时间复杂度和空间复杂度均是O(n)，其中n为字符串的长度。

JAVA代码：

public class Solution {
        public String decodeString(String s) {
            Stack<String> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (']' == c) {
                    StringBuilder stringBuilder = new StringBuilder();
                    while(!stack.peek().equals("[")) {
                        stringBuilder.insert(0, stack.pop());
                    }
                    stack.pop();
                    Integer times = Integer.valueOf(stack.pop());
                    StringBuilder temp = new StringBuilder();
                    for (int j = 0; j < times; j++) {
                        temp.append(stringBuilder);
                    }
                    stack.push(temp.toString());
                } else if (c >= '0' && c <= '9'){
                    StringBuilder stringBuilder = new StringBuilder();
                    while (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                        stringBuilder.append(s.charAt(i));
                        i++;
                    }
                    i--;
                    stack.push(stringBuilder.toString());
                } else {
                    stack.push(s.substring(i, i + 1));
                }
            }
            StringBuilder result = new StringBuilder();
            while (!stack.isEmpty()) {
                result.insert(0, stack.pop());
            }
            return result.toString();
        }
    }

LeetCode解题报告：

![20190529135548374.png][]

### 思路二：递归 ###

在思路一中，我们使用的是自己建的栈，实际上递归本身就是在调用系统栈，因此本题也可以用递归来解决。

为了在递归的过程中依次从左往右遍历字符串，设置一个int型成员变量i来控制对字符串中字符的遍历。

时间复杂度和空间复杂度均是O(n)，其中n为字符串的长度。

JAVA代码：

public class Solution {
        private int i = 0;
        public String decodeString(String s) {
            return decode(s).toString();
        }
        private StringBuilder decode(String s) {
            StringBuilder result = new StringBuilder();
            int count = 0;
            while (i < s.length()) {
                char c = s.charAt(i);
                i++;
                if (c >= '0' && c <= '9') {
                    count *= 10;
                    count += c - '0';
                } else if (c == '[') {
                    StringBuilder stringBuilder = decode(s);
                    for (int j = 0; j < count; j++) {
                        result.append(stringBuilder);
                    }
                    count = 0;
                } else if (c == ']') {
                    return result;
                } else {
                    result.append(c);
                }
            }
            return result;
        }
    }

LeetCode解题报告：

![20190529143120224.png][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_decode-string]: https://leetcode-cn.com/problems/decode-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220126/885003e38133456f949a102fd38b669e.png
[20190529135548374.png]: /images/20220126/f180dbe6f2054d47af05327344139b84.png
[20190529143120224.png]: /images/20220126/b0e03459a31a442ab88274d79b7dfb93.png