394. Decode String.md

394. Decode String

思路

给定一个编码后的字符串，根据规则对其解码。

思路一、递归

由题意知，由于k[encoded_string]中的encoded_string内部依然可能包含k[encoded_string]这种形式，所以我们可以用递归求解。 我们用res表示当前已经解码好的字符串，用两个指针l和r分别代表子串的左右边界，然后用brackets_count表示待配对的括号数，则有以下几种情况:

1. 如果s[r] >= '0' && s[r] <= '9' && brackets_count == 0: 说明此时s.substr(l, r-l)是一个普通的串，无需解码， 即res += s.substr(l, r-l)即可。由于此时s[r]是数字（即一个数的开头），所以我们还需用一个变量k记录这个数，留在下次用。
2. 否则，如果s[r] == '['，待配对的括号数加一个，即brackets_count++。
3. 否则，如果s[r] == ']'，待配对的括号数减一个，即brackets_count--。另外如果此时brackets_count等于0了， 说明此时s.substr(l, r-l)就是一个需要递归调用解码函数的子串，而且别忘了次数k，所以res加k次decodeString(s.substr(l, r-l))即可。
4. 否则，即普通字符，那么r++即可（注意上述三种情况最后也需要合理更新l和r）。

思路二、迭代

此题也可以用迭代的解法，用两个stack，stk1记录待每层的子串（层按括号划分），stk2记录次数k，我们用一个指针i从前往后遍历， 用cur_str记录当前层的字符串，

1. 当s[i] >= '0' && s[i] <= '9'，说明遇到了数字，这代表下一层子串将要重复的次数，我们需要将其入栈stk2;
2. 否则，若s[i] == '['，说明即将进入下一层，那么应该把当前层子串cur_str入栈stk1然后清空cur_str；
3. 否则，若s[i] == ']'，说明当前层结束，那么应该从stk1中pop出上层子串pre_str，从stk2中pop出当前层子串的重复次数k，然后将pre_str加上k次cur_str；由于现在是当前层结束，应回到上一层，所以更新cur_str = pre_str；
4. 否则，则仍处于当前层，cur_str += s[i]即可。

最后会回到最顶层，cur_str即结果。

C++

思路一

class Solution {
public:
    string decodeString(string s) {
        if(s.size() == 0) return "";
        string res = "";
        int l = 0, r = 0;
        int brackets_count = 0, k = -1;
        while(r < s.size()){
            if(s[r] >= '0' && s[r] <= '9' && !brackets_count){
                res += s.substr(l, r-l);
                l = r;
                while(r < s.size() && s[r] >= '0' && s[r] <= '9') r++;
                k = stoi(s.substr(l, r-l));
                l = r + 1;
                r -= 1; // 后面要加1所以这里先减去1
            }
            else if(s[r] == '[') brackets_count++;
            else if(s[r] == ']'){
                if(--brackets_count == 0){
                    while(k--)
                        res += decodeString(s.substr(l, r-l));
                    l = r + 1;
                }
            }
            r++;
        }
        return res + s.substr(l, r-l);
    }
};

思路二

class Solution {
public:
    string decodeString(string s) {
        if(s.size() == 0) return "";
        stack<string>stk1;
        stack<int>stk2;
        
        int i = 0;
        string cur_str = ""; // 当前层的子串
        while(i < s.size()){
            if(s[i] >= '0' && s[i] <= '9'){
                int j = i;
                while(j < s.size() && s[j] >= '0' && s[j] <= '9') j++;
                stk2.push(stoi(s.substr(i, j-i)));
                i = j - 1; // 后面要加1所以这里先减去1
            }
            else if(s[i] == '['){ // 新的一层
                stk1.push(cur_str); // 将上一层入栈
                cur_str = ""; // 新的一层初始化
            }
            else if(s[i] == ']'){ // 当前层结束, 回到上一层
                string pre_str = stk1.top(); stk1.pop();
                int k = stk2.top(); stk2.pop();
                while(k--) pre_str += cur_str;
                cur_str = pre_str; // 回到上一层
            }
            else cur_str += s[i];
            
            i++;
        }
        return cur_str;
    }
};