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

 

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

 

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

 

开局思路

 

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

 

在中括号层次比较深的情况下，如何完成回溯，将当前的字符与之前的字符拼接。

 

当出现次数并不是个位数，而是类似100，1000 这样的多位数，如何来解析。

 

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

 

利用栈

 

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

 

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

 

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

 

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

 

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

 

- 4. 遇到 ], 取出栈中multi值，将当前的 res 字符串重复 multi 次，赋值给临时变量tmp，然后让另一个存放累积字符串的栈中弹出栈顶元素和当前的tmp拼接，作为最新的累积字符串赋值给res。

 

如果现在没看懂，没有关系，给出代码就明白了，让大家直观感受一下:

 

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;

 

};

 

利用递归程序

 

递归的思路就容易一点，一旦遇到[，立马进入新的递归程序，扫描到对应的]为止。也就是说，凡是遇到括号，括号里面的事情，全部交给子程序完成。建议大家看完代码再来体会这句话:

 

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. 考察对递归和回溯思想的理解。(其实字符串拼接就是向前回溯的过程)

 

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

 

它其实具有着天然的递归性质，只是我们初学的时候，容易先入为主地把这种先入后出的数据结构想的太简单。