leedcode 394. 字符串解码(栈,模拟)

题目描述

难度:中等

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"
示例 3:

输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"
示例 4:

输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

输入:s = "10[a]"
输出:"aaaaaaaaaa"

题解

  • 思路算法都能想到,有很多细节没考虑周全,花了不少时间
  • 本题中可能出现括号嵌套的情况,比如 2[a2[bc]],这种情况下我们可以先转化成 2[abcbc],在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TOKEN,并用栈来维护这些 TOKEN。具体的做法是,遍历这个栈:

    如果当前的字符为数位,解析出一个数字(连续的多个数位)并进栈
    如果当前的字符为字母或者左括号,直接进栈
    如果当前的字符为右括号,开始出栈,一直到左括号出栈,出栈序列反转后拼接成一个字符串,此时取出栈顶的数字,就是这个字符串应该出现的次数,我们根据这个次数和字符串构造出新的字符串并进栈

    作者:LeetCode-Solution
    链接:https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • 注意,字符转字符串 string ss(1,字符) 
class Solution {
public:
    string decodeString(string s) {
        stack<int>num_stk;//数字栈
        stack<string>char_stk;//字符串栈 注意是字符串
        string ans="";//存放最终结果
        int n=s.length();
        for(int i=0;i<n;i++){
            cout<<s[i]<<endl;
            if(isdigit(s[i])){//判断是否为数字 数字不一定只有一位 比如会有 100
                int tmp_num=int(s[i]-'0');
                while(i+1<n&&isdigit(s[i+1])){//如果下一位也是数字 
                    tmp_num=tmp_num*10+int(s[i+1]-'0');
                    i++;
                }
                num_stk.push(tmp_num);//放入数字栈
            }else if(s[i]=='['){
                string ss(1,s[i]);//要将字符转为字符串
                char_stk.push(ss);//放入字符串栈
            }else if(s[i]==']'){//在最近 '[' 前的所有字符都弹出合并 解码再放入
                int tmp_num=num_stk.top();//弹出最近的数
                num_stk.pop();

                string tmp_char="";
                string tmp_new_char="";

                while(char_stk.top()!="["){//先把最近 '[' 前的所有字符都弹出合并
                    tmp_char=char_stk.top()+tmp_char;
                    char_stk.pop();
                }            
                for(int j=0;j<tmp_num;j++){//再根据弹出的数 对tmp_char重复多次
                    tmp_new_char+=tmp_char;
                }
                char_stk.pop(); //记得弹出 '['
                if(char_stk.empty()){//如果此时字符串栈已经空了
                    ans+=tmp_new_char;//就把当前解码好的字符串和最终ans合并
                }else{
                    char_stk.push(tmp_new_char);//如果没空 说明栈中还有'[' 记得把结果放回栈中
                }           	
                
            }else{
                string ss(1,s[i]);//如果是字符 就转为字符串
                char_stk.push(ss); //放入字符串栈中
            }
        }
        string other="";//最后注意 栈中可能还有一些剩余字符 记得合并到ans中
        while(!char_stk.empty()){//比如 s = "2[abc]3[cd]ef" 中的 "ef"
            other = char_stk.top()+other;
            char_stk.pop();
        }
        ans+=other;
        return ans;
    }
};

leedcode 394. 字符串解码(栈,模拟)

  • 官方用不定长数组来模拟栈操作,方便从栈底向栈顶遍历
class Solution {
public:
    string getDigits(string &s, size_t &ptr) {
        string ret = "";
        while (isdigit(s[ptr])) {
            ret.push_back(s[ptr++]);
        }
        return ret;
    }

    string getString(vector <string> &v) {
        string ret;
        for (const auto &s: v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s) {
        vector <string> stk;
        size_t ptr = 0;

        while (ptr < s.size()) {
            char cur = s[ptr];
            if (isdigit(cur)) {
                // 获取一个数字并进栈
                string digits = getDigits(s, ptr);
                stk.push_back(digits);
            } else if (isalpha(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.push_back(string(1, s[ptr++])); 
            } else {
                ++ptr;
                vector <string> sub;
                while (stk.back() != "[") {
                    sub.push_back(stk.back());
                    stk.pop_back();
                }
                reverse(sub.begin(), sub.end());
                // 左括号出栈
                stk.pop_back();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = stoi(stk.back()); 
                stk.pop_back();
                string t, o = getString(sub);
                // 构造字符串
                while (repTime--) t += o; 
                // 将构造好的字符串入栈
                stk.push_back(t);
            }
        }

        return getString(stk);
    }
};
  • 递归 见官方

上一篇:【C语言】库函数的模拟实现


下一篇:EXCEL多个sheet页进行合并为一个sheet