394. Decode String - cocoder39/coco39_LC GitHub Wiki

394. Decode String

Notes 2022

class Solution:
    def decodeString(self, s: str) -> str:
        num = 0
        stack = [''] # add '' at beginging or encoutering '['
        for ch in s:
            if ch.isdigit():
                num = 10 * num + int(ch)
            elif 'a' <= ch <= 'z':
                stack[-1] += ch
            elif ch == '[':
                stack.append(num)
                stack.append('')
                num = 0
            else: # ch == ']'
                str1 = stack.pop()
                repeat = stack.pop()
                str2 = stack.pop()
                stack.append(str2 + str1 * repeat) # merge with prev str
        return stack[0]

======================================================================

class Solution {
public:
    string decodeString(string s) {
        int idx = 0;
        return decode(s, idx);
    }
private:
    string decode(string& s, int& idx) {
        string res;
        int n = 0;
        while (idx < s.length() && s[idx] != ']') {
            if (! isdigit(s[idx])) {
                res += s[idx++];
            } else {
                int n = 0;
                while (idx < s.length() && isdigit(s[idx])) {
                    n = n * 10 + (s[idx++] - '0');
                } 
                
                
                idx++; // s[idx] == '[' 
                string t = decode(s, idx); // t.length() <= the distance from last '[' to its paired ']'
                for (int i = 0; i < n; i++) {
                    res += t;
                }
                idx++; // s[idx] == ']'
            }
        }
        return res;
    }
};