LeetCode394——字符串解码-蒲公英云

LeetCode394——字符串解码

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：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解题报告：

思路二：递归

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

为了在递归的过程中依次从左往右遍历字符串，设置一个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;
    }
}