394. Decode String

這題其實是一個基本的遞迴, 但要熟練string跟細節理解

我們可以先建造一個decode, 然後從頭開始掃, 一旦遇到”l”就跳出, 在遇到”]”一定會先邂逅一些數字跟”[”還有一些字串

我們先判斷數字, 因為左括號一定會在數字的後面, 決定好數字, 我們就把這個string再往下做一次, 一旦下面那層的i 收集到右括號後, 就會回傳他在這之間的string, 那下層string也有左括號怎麼辦, 就是遞迴再往下做

cclass Solution {
  public:
    string decode(string s, int &i) {
        string res = "";
        int n = s.size();
        while (i < n && s[i] != ']') {
            if (s[i] < '0' || s[i] > '9') {
                res += s[i];
                i++;
            } else {
                int count = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    count = count * 10;
                    count += s[i] - '0';
                    i++;
                }
                i++;
                string t = decode(s, i);
                i++;
                while (count > 0) {
                    res += t;
                    count--;
                }
            }
        }
        return res;
    }
    string decodeString(string s) {
        int i = 0;
        return decode(s, i);
    }
};

另外一個版本比較接近我一開始想的，但我寫不出來QQ, 去網路上先抄別人的練習

class Solution {
  public:
    string decodeString(string s) {
        stack<int> numst;
        stack<string> strst;
        string t = "";
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count = count * 10;
                count += s[i] - '0';
            } else if (s[i] == '[') {
                numst.push(count);
                count = 0;
                strst.push(t);
                t.clear();
            } else if (s[i] == ']') {
                int number = numst.top();
                numst.pop();
                for (int j = 0; j < number; j++) {
                    strst.top() += t;
                }
                t = strst.top();
                strst.pop();
            } else {
                t += s[i];
            }
        }
        return t;
    }
};