Leetcode 每日一题：Decode String

写在前面：

最近求职季找工作忙的焦头烂额，同时这个学期的助教工作也比之前的工时多了一倍，昨天又拖更了真的对不起大家～～

今天我们来看一道稍微轻松一点的题，这道题目来源于 Valid Parenthesis，不过在这个基础上对其进行了一定的拓展和难度加深。同样是利用括号的一个“深度优先的”场景，也同样可以利用 stack 进行解决，就让我们一起来看看吧！

题目介绍：

题目信息：

• 题目链接：https://leetcode.com/problems/decode-string/description/
• 题目类型：String，Array，Stack
• 题目难度：Medium
• 题目来源：Google 高频面试题

题目问题：

• 给定一个 string 字符串
• 字符串中包含数字，和中括号
• 举例：
  • 100[abc] 代表这个 abc 要被重复一百次
  • 3[2[ab]] 代表 ab要被重复两次，而重复两次的结果 abab 则又要被重复三次，即 3 * abab
• 返回完整的解码字符串

题目想法：

这道题用中括号来进行解码不部份的划分，我们可以很容易联想到我们之前做过的 Leetcode Valid Parenthesis，因为括号内嵌括号的问题正好可以利用类似的 stack 数据结构来进行解决。

首先，我们依旧是将所有的原 string 中每一个 char 的元素都放进 stack 中，这样能记录我们的先后顺序，也便于我们后续的操作

而每当我们 iterate 到一个 ']' 括号的时候，我们需要在 stack 中往回找最近的 上一个 ‘[' 在哪里，在找到之后，这两个括号之间的所有 char 字母将会被组合在一起成为一个需要 decode string。我们再从 '[' 前面找，将他前面所有所包含的数字找出来，并将它转化为整数，这个数就是我们需要对这个 decode string 的重复次数。

我们将对应的 decode string 重复对应的次数以后，由尾到头倒序的插回 stack 中，因为 stack 是 LIFO，所以倒叙插入可以保证我们之前取出来的 decode string 在顺序是反的情况下能被正确的插入回去。

在插入回去的时候，我们是将 decode string 的每一个 char 一个个的插入回去，并重复 n 次。

最后，我们将 stack 中的所有元素再全部倒序的提取出来，就是我们想要的 string 了！

题目解法：

• 定义一个 stack<char>
• 顺序遍历原 string：
  • 如果不是‘]'：
    • 将对应的 char 放入 stack 中
    • 前进到下一次遍历
  • 定义 decode string
  • 遍历直到 stack 的 top 元素是 ‘['
    • decode string += 当前元素
  • stack.pop 去除 [
  • 定义数字 num
  • 遍历直到 stack 为空或者当前 top 不再是数字：
    • num += 当前元素
  • 将 num 转化为整数元素
  • 遍历 num 次：
    • 从后往前遍历 decoded string：
      • 将当前元素插入回 stack
• 遍历 stack
  • 倒序组合所有元素
• 返回结果

题目代码：

class Solution {
public:
    string decodeString(string s) {
        stack<char> track;
        
        for(char ch: s){
            if(ch != ']'){
                track.push(ch);
                continue;
            }
            
            //find the previous bracket
            string repeated = "";
            while(track.top() != '['){
                repeated += track.top();
                track.pop();
            }
            
            //find the repeated time;
            track.pop();  //get rid of the [
            string num;
            while(!track.empty() && isdigit(track.top())){
                num += track.top();
                track.pop();
            }
            reverse(num.begin(), num.end());
            int numRepeats = stoi(num);
            
            //reverse the repeat string and repeat for that amount of time:
            //push the intermediete res back to the stack
            for(int i = numRepeats - 1; i >= 0; i--){
                for(int k = repeated.size()-1; k >= 0; k--){
                    track.push(repeated[k]);
                }
            }
        }
        
        //construct everything together
        string finalR;
        while(!track.empty()){
            finalR = track.top() + finalR;
            track.pop();
        }
        return finalR;
    }
};