简要介绍

大家好，我是神三元。今天给大家分享一道有意思的算法题，在leetcode平台上截图如下:

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

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

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

开局思路

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

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

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

利用栈

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

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

1. 遇到数字, 直接参加计算，累积multi值。
1. 遇到普通字符(除[,]外)，累积到 res 后面。
1. 遇到 [, 将之前累积的字符串res压栈，当前multi值压到另一个栈。然后当前 multi归零，res置空。
1. 遇到 ], 取出栈中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;
}

两种方法都顺利通过。

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

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

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

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

❤️ 看完两件事

如果你觉得这篇内容对你挺有启发，我想邀请你帮我两个小忙：

点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
关注公众号「前端三元同学」，每日坚持灵魂之问，遇见更好的自己！

五分钟带你领略: 腾讯半年来出现最频繁的算法之一——字符串解码

简要介绍

开局思路

利用栈

利用递归程序

❤️ 看完两件事