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
- 从后往前遍历 decoded string：
- 如果不是‘]'：
- 遍历 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;
}
};原文地址：https://blog.csdn.net/2401_85421495/article/details/142268751
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！