侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【栈, 递归】字符串解码

GabrielxD
2022-05-14 / 0 评论 / 0 点赞 / 46 阅读 / 1,935 字 / 正在检测是否收录...

题目

394. 字符串解码


给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"

示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"

示例 3:

输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"

示例 4:

输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

提示:

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

解题

方法一:栈

思路

维护一个栈(stack),遍历字符串:

  • 如果当前字符(curr)是数字,解析出一个重复次数(repeat)并入栈。(具体解析见方法三说明)
  • 如果当前字符是字母或 '[',直接把当前字符入栈。
  • 如果当前字符是 ']' ,说明整个字符串中某一个可解析部分已经全部入栈,且在栈顶的区域,可以开始解析: 开始出栈,把遇到 '[' 之前的字符全部出栈并反向拼入重复部分(repeating)(与入栈的顺序相反),把 '[' 出栈,此时的栈顶元素就是该重复部分的重复次数(repeat),把它出栈并转为整数,新建一个容器(decoded)把 repeating 拼接 repeat 次,最后把 decoded 入栈,表明解析完成。

完成遍历后,把栈中的元素全部出栈,并反向拼入答案(此时栈中的元素个数其实就是原字符串中第一层需解析字符串部分(encoded_string)的个数,如 test2[ab2[e10[a]]c]3[c5[z]d]ef 遍历完成后,stack 的大小应为 2 (2[ab2[e10[a]]c]3[c5[z]d]))。

代码

class Solution {
    public String decodeString(String s) {
        Deque<String> stack = new LinkedList<>();
        for (int i = 0 ; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (isDigit(curr)) {
                // 当前字符为数字时 解析重复次数
                StringBuilder repeat = new StringBuilder(String.valueOf(curr));
                for (curr = s.charAt(++i); isDigit(curr); curr = s.charAt(++i)) {
                    repeat.append(curr);
                }
                // 之所以这里要自减是因为for循环体中已经定义了自增
                // 而这里解析重复次数时由于要验证下一个字符还是不是数字
                // 所以i不可避免的会向后移动一位, 为了避免跳过字符所以自减
                i--;
                stack.push(repeat.toString());
            } else if (curr != ']') {
                // 因为字符串中只可能有小写英文字母、数字、'['、']'
                // 所以排除数字和']'就是这个条件
                stack.push(String.valueOf(curr));
            } else {
                // 当前字符为']'时
                StringBuilder repeating = new StringBuilder();
                while (!"[".equals(stack.peek())) {
                    // 每次都加在sb的开头, 达到反向的目的
                    repeating.insert(0, stack.pop());
                }
                stack.pop(); // 把'['出栈
                // 获取目前栈顶的当前部分对应的重复次数
                int repeat = Integer.parseInt(stack.pop());
                StringBuilder decoded = new StringBuilder();
                // 拼入容器
                for (; repeat > 0; repeat--) decoded.append(repeating);
                stack.push(decoded.toString());
            }
        }
        StringBuilder ans = new StringBuilder();
        // 出栈并反向加入答案中
        while (!stack.isEmpty()) ans.insert(0, stack.pop());
        return ans.toString();
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
}

方法二:递归

思路

从左向右解析字符串:

  • 如果当前字符为数字,那么后面一定包含一个用方括号表示的字符串,即属于这种情况:k[...]
    • 可以先解析出重复次数(repeat),然后解析到了 '[',递归向下解析后面的内容,遇到对应的 ']'就返回,此时可以根据解析出的数重复次数和解析出的括号里的字符串(repeating)构造出一个新的字符串(decoded : $decoded = repeat \cdot repeating$)。
    • k[...] 解析结束后,再次调用递归函数,解析 ']' 右边的内容。
  • 如果当前字符是字母,那直接解析当前这个字母,然后递归向下解析这个字母后面的内容。

代码

class Solution {
    private String str;
    private int pointer, len;

    public String decodeString(String s) {
        str = s;
        pointer = 0;
        len = s.length();
        return decodeString();
    }

    private String decodeString() {
        // 结束条件: 当前字符为']'或遍历完成
        if (pointer == len || str.charAt(pointer) == ']') return "";
        char curr = str.charAt(pointer);
        if (isDigit(curr)) {
            // 如果当前字符是数字 解析出一个重复次数
            int repeat = curr - '0';
            for (curr = str.charAt(++pointer); isDigit(curr);
                 curr = str.charAt(++pointer)) {
                repeat = repeat * 10 + (curr - '0');
            }
            pointer++; // 跳过 '['
            // 递归向后解析'[]'中的内容
            String repeating = decodeString();
            // 拼接字符串 decoded = repeat * repeating
            StringBuilder decoded = new StringBuilder();
            for (; repeat > 0; repeat--) decoded.append(repeating);
            // 当前区域解析完成指针向后移动一位
            pointer++;
            // 返回当前解析结果+递归后面的解析结果
            return decoded.append(decodeString()).toString();
        } else if (curr != '[') {
            // 如果当前字符是字母直接解析当前这个字母,然后递归向后解析这个字母后面的内容
            pointer++;
            return String.valueOf(curr) + decodeString();
        }
        return decodeString();
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
}

方法三:栈 递归

思路

新建一个栈,用来存放 '[' 的索引

遍历字符串:

  • 如果当前字符是数字,说明遍历到了重复的次数 k:
    • 如果此时栈不为空,则现在正在待解码的子字符串中,直接跳过该字符
    • 记录重复次数 repeat 因为重复次数最大可能是三位数,所以要看后面的字符是否是重复次数的一部分
    • 所以循环下一个字符,如果不是数字就跳出,如果是数字,就加入重复次数的记录中
  • 如果当前字符是 '[',说明遍历到了待解码子字符串(encoded_string)的开始标识:
    • 直接把 当前索引+1 进栈,作为该 encoded_string 的开始索引
  • 如果当前字符是 ']',说明遍历到了待解码子字符串的结束标识:
    • 把对应的开始索引弹出栈
    • 如果弹出后栈还不为空的话,说明这是第二层甚至更深的 encoded_string 当前遍历不需要处理,直接跳过进行下一次循环
    • 这是第一层第一个遇到的 encoded_string ,截取其前面的部分(before$ = s[0, repeatStart)$)用于拼接,截取需要处理的 encoded_string 区(repeating$ = s[start, i)$),截取后面的部分(after$ = s[i + 1, len)$)
    • 因为 repeatingafter 中还可能有需要解码的 encoded_string ,把它们递归地做解码
    • 解码完成后,把前面的部分(before)拼入 repeat 次的重复部分(repeating)后再拼接上前面的部分即为解码后的字符串,直接返回

代码

class Solution {
    public String decodeString(String s) {
        Stack<Integer> stack = new Stack<>();
        if (!s.contains("[")) return s;
        int len = s.length();
        int repeatStart = 0, repeat = 0;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (isDigit(ch)) {
                if (!stack.isEmpty()) continue;
                repeat = ch - '0';
                repeatStart = i;
                for (char next = s.charAt(i + 1); isDigit(next); i++, next = s.charAt(i + 1)) {
                    repeat = repeat * 10 + (next - '0');
                }
            } else if (ch == '[') {
                stack.push(i + 1);
            } else if (ch == ']') {
                int start = stack.pop();
                if (!stack.isEmpty()) continue;
                StringBuilder before = new StringBuilder(s.substring(0, repeatStart));
                String repeating = decodeString(s.substring(start, i));
                String after = decodeString(s.substring(i + 1, len));
                for (; repeat > 0; repeat--) before.append(repeating);
                return before.append(after).toString();
            }
        }
        return s;
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
}
0

评论区