当前位置：首页 > article >正文

Leetcode 每日一题：Decode String

article 2024/9/23 13:21:01

写在前面：

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

今天我们来看一道稍微轻松一点的题，这道题目来源于 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;
    }
};

查看全文

http://www.kler.cn/news/304766.html