leetcode 349 lintcode 575--dfs+stack

图片.png

图片.png

这个题吧，用dfs还是很简单的。将括号里面的一切当成另一个崭新的dfs. 大循环里面 要么是string 要么是数字

dfs:

//dfs:
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++];
        }
        else {
            int cnt = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                cnt = cnt * 10 + s[i++] - '0';
            }
            ++i;
            string t = decode(s, i);
            ++i;
            while (cnt-- > 0) {
                res += t;
            }
        }
    }
    return res;
}
string decodeString(string s) {
    int i = 0;
    return decode(s, i);
}

stack:

//my
class Solution {
public:
    string decodeString(string s) {
        stack<int> num;
        stack<string> data;
        int i = 0; int n = s.size(); int cnt = 0;
        string temp = "";
        while (i < n) {
            if (s[i] >= '0' && s[i] <= '9') {
                cnt = cnt * 10 + s[i] - '0';
            }
            else if (s[i] == '[') {
                num.push(cnt);
                data.push(temp);
                cnt = 0; temp = "";
            }
            else if (s[i] == ']') {
                int n = num.top(); num.pop();
                for (int i = 0; i < n; i++)
                    data.top() += temp;
                temp = data.top();
                data.pop();
            }
            else {
                temp += s[i];
            }
            i++;
        }
        return data.empty() ? temp : data.top();
    }
};