Decode String

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:

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

比较简单的一道题，先分析一下题目，首先输入的格式是k[encoded_string]，要将其扩展成k 个 encoded_string 组成的字符串，我们暂且先不考虑嵌套的情况，我们通过一个简单的状态机就可以解决这个问题：

有限状态机

这个代码写起来也很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string decodeString(string s) {
    string res;
    string temp;
    int num = 0;
    for(int i = 0, size = s.size(); i < size; i++) {
        if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        } else if (s[i] == '[') {
            res += temp;
           	temp = "";
        } else if (s[i] == ']') {
            for(int i = 0;i < num;i++)
            	res += temp;
            temp = "";
        } else { // charar
            temp.push_back(s[i]);
            num = 0;
        }
    }
    return res;
}

如果这道题不需要考虑嵌套问题的话，上面就是正确的答案了。虽然需要处理嵌套的问题，但是其实只需要用栈来模拟多个层次的嵌套即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
string decodeString(string s) {
    int num = 0;

    stack<string> sst;
    stack<int> nst;
    nst.push(1);
    sst.push(string());

    for(int i = 0, size = s.size(); i < size; i++) {
        if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        } else if (s[i] == '[') {
            beg = end = i + 1;
            nst.push(num); num = 0;
            sst.push(string());
        } else if (s[i] == ']') {
            string s = sst.top(); sst.pop();
            int n = nst.top(); nst.pop();
            for(int j = 0;j < n;j++) sst.top() += s;
        } else { // char
            sst.top().push_back(s[i]);
        }
    }
    return sst.top();
}

update at 2020-04-04

似乎最上面那个代码是有问题的，emmm，不管了，更新一个用一个stack的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string decodeString1(string s) {
    stack<pair<int, string>> st;
    st.push(make_pair(1, ""));
    int num = 0;
    for(auto c: s) {
        if (isdigit(c)) {
            num  = num * 10 + c - '0';
        } else if (c == '[') {
            st.push(make_pair(num, ""));
            num = 0;
        } else if (c == ']') {
            auto p = st.top(); st.pop();
            int n  = p.first;
            auto s = p.second;
            // cout << n << s << endl;
            for(int i = 0; i < n; i++) st.top().second += s;
        } else {
            st.top().second.push_back(c);
        }
    }
    return st.top().second;
}