66-字符串解码

自己的做法

算法思想

使用两个栈，count栈一个放数字，chars放字符。

遍历字符串，有以下几种可能情况：

• 是数字，因为有可能是大于9的。那么就从当前字符开始，往后遍历，将遍历到的数字字符转换为数字加到num上，直到遇到第一个不是数字的字符，将num添加到count栈中
• [：直接入栈
• ]：遇到]代表需要将该括号内的字符，循环counr.top()遍，所以chars依次出栈，并添加到temp字符串中，直到遇到[(一定会遇到)。此时temp就是中括号内的字符串。这时有两种情况：
  • 栈不为空：说明该字符串序列嵌套在另一个中括号内，如"3[a2[b]]"，那么就应该将temp字符串的字符循环count.top()遍，放入chars栈中
  • 栈为空：说明该字符串序列并没有嵌套在其他中括号内，可以直接循环count.top()遍添加到结果字符串res中
• 字符：分两种情况：
  • chars不为空：说明该字符在一个中括号内，直接入栈chars
  • chars为空：说明该字符串是单独出现的，不需要循环。添加到res中

算法实现

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        stack<char> chars;
        stack<int> count;
        for(int index = 0; index < s.size(); index++) {
            char ch = s[index];
            if(isdigit(ch)) {
                int num = 0;
                while (isdigit(s[index])) {
                    num = num * 10 + (s[index++] - '0');
                }
                //因为index在循环处要加1，所以这里要减1
                index--;
                count.push(num);
            } else if(ch == '[') {
                chars.push(ch);
            } else if(ch == ']') {
                string temp = "";
                while (chars.top() != '[') {
                    temp = chars.top() + temp;
                    chars.pop();
                }
                //弹出`[`
                chars.pop();
                if(!chars.empty()) {
                    for(int i = 0; i < count.top(); i++) {
                        for(int j = 0; j < temp.size(); j++) {
                            chars.push(temp[j]);
                        }
                    }
                } else {
                    for(int i = 0; i < count.top(); i++) {
                        res += temp;
                    }
                }
                count.pop();
            } else {
                if(chars.empty()) {
                    res.push_back(ch);
                } else {
                    chars.push(ch);
                }
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

参考做法

参考给了两种做法，一种和我的类似，只不过它把数字和字母都放到同一个栈，数字紧挨着[。

第二种用到了编译原理的知识。给出了一个LL(1)文法，根据FOLLOW集和FIRST集构造预测分析表。

学过编译原理，但只看懂了一部分。

留个坑。