【经典面试】87 字符串解码

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：“aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：“accaccacc”

示例 3：
输入：s = “2[abc]3[cd]ef”
输出：“abcabccdcdcdef”

示例 4：
输入：s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 ‘[]’ 组成
• s 保证是一个有效的输入。
• s 中所有整数的取值范围为 [1, 300]

题解1 递归(程序栈)——形式语言自动机(LL(1)) : O(S)

class Solution {int idx;
public:int getdigits(string& s){int ret = 0;while(idx < s.size() && isdigit(s[idx])){ret = ret*10 + s[idx++]-'0';}return ret;} string getstring(string& s){// 结束条件if(idx == s.size() || s[idx] == ']')return string("");// 当前字符char cur = s[idx];// 重复次数置1int rep = 1;// 返回值string ret = "";// condition:如果是数字if(isdigit(cur)){int rep = getdigits(s);string str = "";// 跳左括号idx ++;// 顺序很重要：跳完左括号就要 取后面的stringstr = getstring(s);// 跳右括号idx ++;// 后--while(rep--){ret += str;}}// condition：如果是字母else if(isalpha(cur)){ret = string(1, s[idx++]);}return ret+getstring(s);}string decodeString(string s) {idx = 0;return getstring(s);}
};

另一种递归(直观)

class Solution {public:string decodeString(string s) {string res = "";for(int i = 0; i < s.size(); i++){// 字符if(s[i]>='a' && s[i] <= 'z'){res += s[i];// 左括号或者数字}else{int rep = 0;while(s[i] >= '0' && s[i] <= '9'){rep = rep*10 + s[i++]-'0';}int curp = i+1;int lnum = 1;while(lnum){i ++; // i最后是下一次解决的一段字符串的结尾（[[[..]]]，左括号要和右括号数对上）if(s[i] == '[') lnum++;if(s[i] == ']') lnum--;}string str = decodeString(s.substr(curp, i-curp));while(rep --){res += str;}}}return res;}
};

题解2 2个栈(逆波兰式)

class Solution {public:string decodeString(string s) {stack<int> num_stk; // 数字栈stack<string> str_stk; // 字符串栈string res = ""; // 当前累积的字符串// 逆波兰式for(int i = 0; i < s.size(); i++){if(isdigit(s[i])){int tmp = s[i]-'0';while(isdigit(s[++i]))tmp = tmp*10 + s[i]-'0';num_stk.push(tmp);i --; // for 有自增}else if(s[i] == '['){str_stk.push(res); // 把上一段存起来res = ""; // 清空，开始累积该左括号后面的字符串}else if(s[i] == ']'){string tmp = "";int rep = num_stk.top();num_stk.pop();while(rep--)tmp += res;res = str_stk.top() + tmp;str_stk.pop();}else{res += s[i]; }}return res;}
};

1个栈(参考官方，但是不喜欢)

class Solution {
public:string getDigits(string &s, size_t &ptr) {string ret = "";while (isdigit(s[ptr])) {ret.push_back(s[ptr++]);}return ret;}string getString(vector <string> &v) {string ret;for (const auto &s: v) {ret += s;}return ret;}string decodeString(string s) {vector <string> stk;size_t ptr = 0;while (ptr < s.size()) {char cur = s[ptr];if (isdigit(cur)) {// 获取一个数字并进栈string digits = getDigits(s, ptr);stk.push_back(digits);} else if (isalpha(cur) || cur == '[') {// 获取一个字母并进栈stk.push_back(string(1, s[ptr++])); } else {++ptr;vector <string> sub;while (stk.back() != "[") {sub.push_back(stk.back());stk.pop_back();}// sub push的顺序是逆序，累积前需要反过来reverse(sub.begin(), sub.end());// 左括号出栈stk.pop_back();// 此时栈顶为当前 sub 对应的字符串应该出现的次数int repTime = stoi(stk.back()); stk.pop_back();string t, o = getString(sub);// 构造字符串while (repTime--) t += o; // 将构造好的字符串入栈stk.push_back(t);}}return getString(stk);}
};