LeetCode 394. 字符串解码

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

        使用栈来很好的解决每一个中括号(包含前边的数字)的重复插入问题。

        我们首先创建一个栈，栈中的数据是一个个的键值对{count,ans.size()};分别是当前字符串重复的次数，和当前字符串在ans的其实下标。ans代表的是遍历到当前字符的正确答案。

        当遍历到数字的时候我们将其记录下来(使用count记录)。

        当遍历到 '[' 将此时的count与此时的ans的长度(也就是此时这一小段重复元素的起始位置)给记录到栈中。

        当遍历到 ']' 则开始进行对此时的一对中括号中的数进行操作，然后出栈此时的栈顶元素，因为此时栈顶已经被使用过了。

代码

class Solution 
{
public:
    string decodeString(string s) 
    {
        // 该字符串用来记录我们的最终答案
        string ans;
        // 保存[前的数字
        int count=0;
        // 用来存放{count,ans.size()};
        // 分别是当前字符串重复的次数，和当前字符串在ans的其实下标
        stackint,int>> st;
        for(auto&ch:s)
        {
            // 若是数字，则进行记录
            if(isdigit(ch))
            {
                count=count*10+ch-'0';
            }
            // 若是'[' 则将此位置和重复数字组成键值对入栈
            else if(ch=='[')
            {
                st.push({count,ans.size()});
                count=0;
            }
            // 若是字母，则直接插入ans
            else if(isalpha(ch))
            {
                ans+=ch;
            }
            // 若是']'，则开始进行对此时的一对中括号中的数进行操作
            // 然后出栈记录当前中括号中数据的键值对
            else if(ch==']')
            {
                // n就是该短字符串出现的次数
                int n=st.top().first;
                // 根据起始位置和长度进行截取
                string str=ans.substr(st.top().second,ans.size()-st.top().second);
                // 遍历循环插入
                for(int i=0;i-1;i++)
                {
                    ans+=str;
                }
                // 出栈
                st.pop();
            }
        }
        return ans;
    }
};