Abo

算法题:字符串解码 (Decode String)

腾讯半年来出现最频繁的算法之一——字符串解码😑


wallhaven-8387q1

递归依旧要命

题目描述

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

近半年来广受各大公司的青睐,出现非常频繁,在腾讯仅仅半年就出现了17次,如果说给满分给5颗星的话,那么这一题算得上实打实的五星题。

那究竟是什么让这个算法从众多的leetcode题库中脱颖而出,在各个大厂中一而再、再而三地出现呢?

接下来,就让我们解开它的奥秘,领略这个算法到底多么经典!

开局思路

刚开始拿到这道题,看到括号匹配问题,直觉上就想到了利用栈先进后出的性质,来完成前后字符串的拼接。但是后来尝试了很久,发现问题并没有那么简单,主要归纳如下:

  1. 在中括号层次比较深的情况下,如何完成回溯,将当前的字符与之前的字符拼接。
  2. 当出现次数并不是个位数,而是类似100,1000 这样的多位数,如何来解析。

接着,我们利用不同的方法,来一步步来解决这两个棘手的问题。

利用栈

说一下整体思路。扫描一遍字符串,针对不同的字符进行不同的处理:

首先有两个重要的变量,表示重复次数的 multi 值和累积字符串 res。

  1. 遇到数字, 直接参加计算,累积multi值。

  2. 遇到普通字符(除[,]外),累积到 res 后面。

  3. 遇到 [, 将之前累积的字符串res压栈,当前multi值压到另一个栈。然后当前 multi归零,res置空。

  4. 遇到 ], 取出栈中multi值,将当前的 res 字符串重复 multi 次,赋值给临时变量tmp,然后让另一个存放累积字符串的栈中弹出栈顶元素和当前的tmp拼接,作为最新的累积字符串赋值给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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var decodeString = function (s) {
// 存放 【重复次数】 的栈
let countStack = [];
// 存放 【累积字符串】 的栈
let resStack = [];
// 用来累积的字符串 res
let res = "";
// 表示重复次数
let multi = 0;
for (let i = 0; i < s.length; i++) {
let cur = s.charAt(i);
if (cur == '[') {
// 双双压栈,保存了当前的状态
countStack.push(multi);
resStack.push(res);
// 纷纷置空,准备下面的累积
multi = 0;
res = "";
} else if (cur == ']') {
// 遇到 ],表示累积结束,要算账了。
// 【当前的串出现多少次】还保存在栈中,把它取出来
let count = countStack.pop();
let temp = "";
// 让 [ 和 ] 之间的字符串(就是累积字符串res)重复 count 次
for(let i = 0; i < count; i++) {
temp += res;
}
// 和前面已经求得的字符串进行拼接
res = resStack.pop() + temp;
} else if (cur >= '0' && cur <= '9') {
// multi累积
multi = multi * 10 + (cur - '0');
} else {
// 字符累积
res += cur;
}
}
return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
var decodeString = function (s) {
// 从第 0 个元素开始处理
return dfs(s, 0);
};

let dfs = (s, n) => {
let res = "";
// 保存起始索引
let i = n;
// 同上,表示重复的次数
let multi = 0;
while(i < s.length) {
let cur = s.charAt(i);
// 遇到数字,累积 multi 值
if(cur >= '0' && cur <= '9')
multi = multi * 10 + (cur - '0');
else if(cur === '[') {
// 划重点!给子程序,把对应的 ] 索引和括号包裹的字符串返回
// 即tmp 的格式为 [索引,字符串]
let tmp = dfs(s, i + 1);
// 这样下次遍历就是从对应的 ] 后面遍历了,因为当前已经把括号里面的处理完了
i = tmp[0];
// 需要重复的字符串已经返回来了
let repeatStr = tmp[1];
for(let j = 0; j < multi; j++) {
res += repeatStr;
}
// 当前已经把括号里面的处理完,multi 置零,为下一轮遍历准备
multi = 0;
}else if(cur === ']') {
// 遇到了对应的 ] ,返回 ] 索引和括号包裹的字符串
return [i, res];
} else {
res += cur;
}
// 继续遍历
i++;
}
return res;
}

两种方法都顺利通过。

估计做完这道题,仔细回味一下,也能够发现这道题的经典之处了:

  1. 考察对栈这种数据结构的理解
  2. 考察字符串的基本操作,涉及对编程语言的考察
  3. 考察对递归和回溯思想的理解。(其实字符串拼接就是向前回溯的过程)

做完这道题,是不是刷新了自己对于栈这种数据结构的认知呢?

它其实具有着天然的递归性质,只是我们初学的时候,容易先入为主地把这种先入后出的数据结构想的太简单。当然它还有其他神奇的功能,我们放在下一期来分享。