字符串解码

题目

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

  • 示例1：

    1
    2
    输入：s = "3[a]2[bc]"
    输出："aaabcbc"

  • 示例2：

    1
    2
    输入：s = "3[a2[c]]"
    输出："accaccacc"

  • 示例3：

    1
    2
    输入：s = "2[abc]3[cd]ef"
    输出："abcabccdcdcdef"

  • 示例4：

    1
    2
    输入：s = "abc3[cd]xyz"
    输出："abccdcdcdxyz"

提示：

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

 

思路+代码

思路

本题可以采用栈操作解法、递归方法分别完成字符串解码

  1. 栈操作：
    本题中可能出现括号嵌套的情况，比如 2[a2[bc]]，这种情况下我们可以先转化成 2[abcbc]，在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TOKEN，并用栈来维护这些 TOKEN。具体的做法是，遍历这个栈：
  • 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
  • 如果当前的字符为字母或者左括号，直接进栈
  • 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈

重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来，就得到了答案。

  1. 递归从左向右解析字符串：
  • 如果当前位置为数字位，那么后面一定包含一个用方括号表示的字符串，即属于这种情况：k[...]：
    • 我们可以先解析出一个数字，然后解析到了左括号，递归向下解析后面的内容，遇到对应的右括号就返回，此时我们可以根据解析出的数字 xx 解析出的括号里的字符串 x*s
    • 我们把 k[...] 解析结束后，再次调用递归函数，解析右括号右边的内容。
  • 如果当前位置是字母位，那么我们直接解析当前这个字母，然后递归向下解析这个字母后面的内容。

代码实现

  • 栈操作1：

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    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();
    				}
    				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);
    	}
    };

  • 栈操作2：

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution {
    public:
    	string decodeString(string s) {
    		int length = s.length();
    		string num = "";
    		string words = "";
    		stack<int> s_num;
    		stack<string> s_c;

    		for (int i = 0; i < length; i++)
    		{
    			if (s[i] >= '0' && s[i] <= '9')
    			{
    				num += s[i];
    			}
    			else if (s[i] >= 'a' && s[i] <= 'z')
    			{
    				words += s[i];
    			}
    			else if (s[i] == '[')
    			{

    				s_num.push(atoi(num.c_str()));
    				num = "";
    				s_c.push(words);
    				words = "";
    			}
    			else
    			{
    				int temp_num = s_num.top();
    				s_num.pop();
    				string temp_str = "";

    				for (int k = 0; k < temp_num; k++)
    				{
    					temp_str += words;
    				}
    				words = s_c.top() + temp_str;
    				s_c.pop();

    			}
    		}
    		return words;
    	}
    };

  • 递归操作：

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    class Solution {
    public:
    	string src; 
    	size_t ptr;

    	int getDigits() {
    		int ret = 0;
    		while (ptr < src.size() && isdigit(src[ptr])) {
    			ret = ret * 10 + src[ptr++] - '0';
    		}
    		return ret;
    	}

    	string getString() {
    		if (ptr == src.size() || src[ptr] == ']') {
    			// String -> EPS
    			return "";
    		}

    		char cur = src[ptr]; int repTime = 1;
    		string ret;

    		if (isdigit(cur)) {
    			// String -> Digits [ String ] String
    			// 解析 Digits
    			repTime = getDigits(); 
    			// 过滤左括号
    			++ptr;
    			// 解析 String
    			string str = getString(); 
    			// 过滤右括号
    			++ptr;
    			// 构造字符串
    			while (repTime--) ret += str; 
    		} else if (isalpha(cur)) {
    			// String -> Char String
    			// 解析 Char
    			ret = string(1, src[ptr++]);
    		}
    		
    		return ret + getString();
    	}

    	string decodeString(string s) {
    		src = s;
    		ptr = 0;
    		return getString();
    	}
    };

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/gdwjv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。