LeetCode – Decode String

题目：

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

解题：

递归方式实现：

1. 循环处理的条件是到了字符串的末尾或遇到’]’;
2. 遇到数字记录到循环次数n，跳过'[‘,进入递归处理；
3. 字符串处理功能：通过res将那个处理结果字符串累加。
4. 递归处理完成后跳过’]’；

实现：

class Solution {
public:
  
    string decodeString(string s) {
        int i=0; 
        return decodeStringHelper(s, i);
    }
    string decodeString(const string &s, int &i){
        
        string res;
        while(i<s.length() && s[i]!=']'){
            if (!isdigit(s[i])) {
                res += s[i++];
            }
            else {
                int n = 0;
                while(i<s.length() && isdigit(s[i])){
                    n = n*10 + s[i++]-'0';
                }
                i++;  // [
                string t = decodeString(s, i);
                i++;  // ]
                while(n-->0){  // k times
                    res += t;
                }
            }
        }
        return res;
    }
};

解题：

借助栈实现：

1. 遇到字符类型字符串，更新计数n；
2. 遇到'[‘ ,计数压栈，临时字符串变量tmp压栈；
3. 遇到’]’, 取出数字和对应字符串栈的数据，重复n倍；
4. 遇到字母直接加到临时字符串变量tmp中。     

实现：

class Solution {
public:
    string decodeString(string s) {
        string tmp;
        stack<int> numStack;
        stack<string> strStack;
        int n= 0;
        for (int i=0;i<s.size();i++){
            if (isdigit(s[i])){
                n = n*10+s[i]-'0';
            }
            else if (s[i] == '['){
                numStack.push(n);
                n = 0;
                strStack.push(tmp);
                tmp.clear();               
            }
            else if (s[i] == ']'){
                int k = numStack.top();
                numStack.pop();
                
                while(k-->0) // K
                {
                    strStack.top() +=tmp;
                }
                tmp = strStack.top();
                strStack.pop();
                
            }
            else
                tmp += s[i];
        }
        return strStack.size() == 0 ? tmp : strStack.top();
    }
};