LeetCode 394. Decode String 解题报告

题目描述

Given an encoded string, return it’s 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].

示例

s = “3[a]2[bc]”, return “aaabcbc”.

s = “3[a2[c]]”, return “accaccacc”.

s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

限制条件

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路

我的思路：

这道题不难，但是要清楚整个解码过程并且考虑到各种情况却不容易，我就是没有把这两个地方弄清楚，所以各种wrong answer，花了好长的时间针对各种情况去修补代码，最后虽然通过了，但是代码又长又复杂。

我看到这道题，很清楚地知道是要用栈这个数据结构，分别存储找到的重复次数，以及需要重复的编码字符串，解题思路就是遍历一遍字符串，遇到不同的字符时需要做出不同的处理。

1.遇到数字字符，遇到数字字符就需要将其转换为数字，并且要注意重复的次数是会超过9次的，所以像‘100[a]’这种情况是要取得整个100

2.遇到字母字符，遇到字母字符就简单地添加该字符到目前记录的编码字符串中

3.遇到’]’，遇到’]’时要完成解码的功能，即重复编码字符串n次，并且很重要的一点就是正确地更新编码字符串。这里正确是指要处理特殊情况，当前重复后的字符串可能是更大的一个编码字符串的一部分，所以重复后的字符串要跟前后的字符拼接在一起（如果前后有字符的话）

4.遇到’[‘，遇到’[‘的时候要把之前记录的编码字符串压栈，因为接下来的是新的一个编码字符串。

在实现的时候我没有处理好上述的4种情况，所以我的代码很糟糕，就不用看我的代码了，那是我留作以后重温时作对比的，建议都看看参考代码1和参考代码2。参考代码1就是很简洁地实现了上面的四种情况，而参考代码2是用了递归的思想，下面讲讲参考代码2的思路。

其它思路：

另一种思路是使用递归，每次递归都找到最里面的编码部分，用其解码后的字符串替换原来字符串对应的编码部分，最后没有找到编码部分时就表示完成了解码。这思路我也想过，但是没有实现出来，惭愧。而参考代码2的实现灵活地使用各种字符串操作，很具有参考价值。

代码

我的代码

class Solution {
public:
    string decodeString(string s) {
        stack<int> num;
        stack<string> encode;
        string temp;
        string res;

        for (int i = ; i < s.size(); i++) {
            if (isdigit(s[i])) {
                int n = s[i++] - '0';
                while (isdigit(s[i]))
                    n = n *  + (s[i++] - '0');
                num.push(n);
                if (temp != "") {
                    encode.push(temp);
                    temp = "";
                }
            } else if (s[i] == ']') {
                if (temp != "")
                    encode.push(temp);

                int n = num.top();
                num.pop();

                string repeat = encode.top();
                encode.pop();

                string tempRes;
                while (n-- > )
                    tempRes += repeat;

                if (!isdigit(s[i + ]) && s[i + ] != ']' && i < s.size()) {
                    i++;
                    while(!isdigit(s[i]) && s[i] != ']' && i < s.size())
                        tempRes += (char)s[i++];
                    i--;
                }

                if (!num.empty() && !encode.empty())
                    encode.top() += tempRes;
                else
                    encode.push(tempRes);

                temp = "";
            } else if (s[i] != '[')
                temp += s[i];
        }

        while (!encode.empty()) {
            res = encode.top() + res;
            encode.pop();
        }

        return res + temp;
    }
};
           

参考代码1

class Solution {
public:
    string decodeString(string s) {
        stack<string> chars;
        stack<int> nums;
        string res;
        int num = ;

        for (char c: s) {
            if (isdigit(c))
                num = num *  + (c - '0');
            else if (isalpha(c)) {
                res += c;
            } else if (c == '[') {
                chars.push(res);
                nums.push(num);
                res = "";
                num = ;
            } else {
                string tmp = res;
                for (int i = ; i < nums.top() - ; i++)
                    res += tmp;
                res = chars.top() + res;
                chars.pop();
                nums.pop();
            }
        }

        return res;
    }
};
           

参考代码2

class Solution {
public:
    string decodeString(string s) {
        auto left = s.find_last_of('[');

        if (left == string::npos)
            return s;
        else {
            auto nPos = left;
            while (isdigit(s[nPos - ]))
                nPos--;
            int num = stoi(s.substr(nPos, left - nPos));

            int right = s.find_first_of(']', left);
            string tmp = s.substr(left + , right - left - );
            string tmpSum;
            while (num-- > )
                tmpSum += tmp;

            return decodeString(s.substr(, nPos) + tmpSum + s.substr(right + ));
        }
    }
};
           

总结

这道题花了好长的时间，不是在思考解法上，而是在修改上，吃了教训，代码真的是要想清楚了再写，不然很有可能实现不出来，即便实现出来了，代码也是很糟糕的。通过这道题，我复习了一下栈的概念，又从递归的解法里学到了怎样去灵活使用各种字符串的函数，收获还是很大的。

辛苦地填了今天的坑，明天继续下一个，下次真的要自己想清楚再动手写，坚持不懈，努力加油~