394 Decode String

题目

394 Decode String

题解

题目要求：给出以k[encoded_string]形式压缩过的字符串，要求进行字符串的解码，其中k是数字，代表方括号内的字符串的重复次数。

简单地对形如k[encoded_string]的字符串进行解码比较简单，只要把方括号内的字符串提取出来，复制k遍即可。然而，编码有可能是嵌套的，即encoded_string内还存在有形如k[encoded_string]的字符串，在这种情况下简单的提取复制得不到正确的结果。

不管编码如何嵌套，都一定会有最里层的编码，即方括号里只含有字母的编码。对于最里层编码，只需要简单的提取复制即可解码。如果用解码后的字符串替换编码字符串，那么我们只要从里向外一层层地进行解码替换，就能得出正确的结果。

找到最里层编码的一个简单方法是，找到编码字符串中的第一个’]‘，并向前找到最近的’[‘，这样的编码必然是最里层的，因为嵌套的编码必然含有两个或以上的’]‘，而第一个’]‘的前面没有任何’]‘。

就这样，不停地找到并解码替换最里层编码，直到找不到’]‘，此时得出的字符串就是解码后的字符串。

代码

class Solution {
public:
	string decodeString(string s) {
		string result = s;

		size_t right_bracket_pos = result.find_first_of(']');
		while (right_bracket_pos != result.npos)
		{
			decode(result, right_bracket_pos);
			right_bracket_pos = result.find_first_of(']');
		}

		return result;
	}
private:
	void decode(string& result, size_t right_bracket_pos) {
		int left_bracket_pos = 0;
		for (int i = right_bracket_pos; i >= 0; i--)
		{
			if (result[i] == '[') {
				left_bracket_pos = i;
				break;
			}
		}
		int baseLength = right_bracket_pos - left_bracket_pos - 1;

		int number_end = left_bracket_pos - 1;
		int number_begin = 0;
		for (int i = number_end; i >= 0; i--)
		{
			if (!isdigit(result[i])) {
				number_begin = i + 1;
				break;
			}
		}
		int numberLength = number_end - number_begin + 1;

		int repeat = stoi(result.substr(number_begin, numberLength));
		string base = result.substr(left_bracket_pos + 1, baseLength);

		string decode;
		for (size_t i = 0; i < repeat; i++)
		{
			decode += base;
		}

		int replaceLength = right_bracket_pos - number_begin + 1;
		result.replace(number_begin, replaceLength, decode);
	}
};