Decode String

https://leetcode.com/problems/decode-string/description/

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis 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 like3aor2[4].

Thoughts

字符串中数字表示紧跟着后面括号内[]子字符串重复的次数，返回把所有[]按规则展开后的字符串。eval括号问题，递归或栈。由于规则简单，用Basic Calculator类似解法，在遇到左括号时把当前结果res存到stack中, 然后res重置并不断累加新括号内的字符直到遇到新的左括号或右括号。 遇到右括号则把stack中的top抛出和当前res结合。处理数字用额外的一个栈counts和主stack共进退，并在]结合时根据counts.top对res做复制。

Code

/*
 * @lc app=leetcode id=394 lang=cpp
 *
 * [394] Decode String
 */

// @lc code=start
class Solution {
public:
    string decodeString(string s) {
       stack<string> st;
       stack<int> counts;
       int num = 0;
       string res;
       for (const auto c : s) {
           if (c == '[') {
               counts.push(num);
               num = 0;
               st.push(res);
               res.clear();
           } else if (c >= '0' && c <= '9') {
               num *= 10;
               num += c - '0';
           } else if (c == ']') {
               const auto count = counts.top();
               auto t = st.empty() ? "" : st.top();
               for (int i = 0; i < count; ++i) {
                   t += res;
               }
               if (!st.empty()) st.pop();
               counts.pop();
               res = t;
           } else {
               res += c;
           }
       }
       return res; 
    }
};
// @lc code=end

class Solution {
    public String decodeString(String s) {
        Stack<Integer> count = new Stack<>();
        Stack<String> stack = new Stack<>();
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int end = i + 1;
                while (Character.isDigit(s.charAt(end))) {
                    end++;
                } 
                count.push(Integer.parseInt(s.substring(i, end)));
                i = end - 1;
            } else if (c == '[') {
                stack.push(res);
                res = "";
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder(stack.pop());
                int repeatTimes = count.pop();
                for (int j = 0; j < repeatTimes; j++) {
                    tmp.append(res);
                }
                res = tmp.toString();
            } else {
                res += c;
            }        
        }

        return res;
    }
}

Analysis

Errors:

1. 在右括号时不用Push.

时空复杂度O(N).