字符串解码

发表于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

LeetCode每日一题，394.Decode String

先看题目描述

题目大意为给定一个经过编码的字符串，返回解码后的字符串。编码规则为 k[encoded_string]，表示方括号内的字符串恰好重复 k 次，题目保证 k 是正整数，且原始数据中是不包括数字的，数字仅表示重复次数

思路和算法

初始的想法为有两个指针，一个指针 right 用来遍历经过编码的字符串，一个指针 left 用来记录遍历时最后一个 [ 出现的位置，当遍历到 ] 时，字符串的子串 sub[left + 1, right)即为要重复的字符串，此时 left 前面的数字就表示重复的次数 k，因此使 left 回溯到不是数字为止，计算 k 的值为多少，将子串重复 k 次后替换掉字串的 [left + 1, right + 1)部分，再将 left 回溯到上一个 [ 出现的位置，若前面已没有 [ , 则回溯到 0，接着继续移动 right 指针遍历字符串，重复上述过程即可

下面是该算法的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

class Solution {
    public String decodeString(String s) {
        StringBuilder str = new StringBuilder(s);
        int left = 0;
        for (int m = str.length(); m > 0; m--) {
            int right = str.length() - m;
            if (str.charAt(right) == '[') {
                left = right;
            }
            if (str.charAt(right) == ']') {
                StringBuilder tmp = new StringBuilder();
                String subStr = str.substring(left + 1, right);
                left = left - 1;
                if (Character.isDigit(str.charAt(left))) {
                    int i = 1;
                    int count = 0;
                    do {
                        count += i * (str.charAt(left) - '0');
                        i = i * 10;
                        left = left - 1;
                    } while(left >= 0 && Character.isDigit(str.charAt(left)));
                    for (int j = 0; j < count; j++) {
                        tmp.append(subStr);
                    }
                }
                str.replace(left + 1, right + 1, tmp.toString());
                while(left >0 && str.charAt(left) != '[' ) {
                    left--;
                }
            }
        }
        return str.toString();
    }
}

之后看题解时，看到一个题解使用的是辅助栈法，算法和代码更加简洁，算法如下

辅助栈法

  • 本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应

  • 算法流程

  1. 构建两个辅助栈，一个stack_multi，存储重复次数，一个stack_res，存储当前字符串，之后遍历字符串 s 中每个字符 c ；

    • 当 c 为数字时，将数字字符转化为 multi，用于后续倍数计算

    • 当 c 为字母时，在 res 尾部添加 c

    • 当 c 为 [ 时，将当前 multi 和 res 入栈，入栈后将 multi 置为 0，res 置为空

      • 记录此 [ 前的临时结果 res 入栈，用于发现对应 ] 后的拼接操作

      • 记录此 [ 前的倍数 multi 入栈，用于发现对应 ] 后，获取 multi * […]的字符串

      • 进入到新 [ 后，multi 和 res重新记录

    • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中

      • last_res 是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 “a”

      • cur_multi 是当前[ 到 ] 内字符串的重复次数，例如 “3[a2[c]]” 中的 2

  2. 返回字符串 res

下面是根据此算法实现的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        LinkedList<Integer> stack_multi = new LinkedList();
        LinkedList<String> stack_res = new LinkedList();
        int multi = 0;
        for(Character c: s.toCharArray()) {
            if (c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int curMulti = stack_multi.removeLast();
                for(int i = 0; i < curMulti; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            } else if (Character.isDigit(c)) multi = multi * 10 + (c - '0');
            else res.append(c);
        }
        return res.toString();
    }
}