LeetCode刷题——394. 字符串解码(HOT100)

发布时间:2024年01月16日

???🌈大家好!本篇文章将较详细介绍栈的题目394. 字符串解码,提供栈和递归两种解法。代码语言为:C++代码😇。


394. 字符串解码

🔒1、题目:

给定一个经过编码的字符串,返回它解码后的字符串。

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

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

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数k ,例如不会出现像 3a2[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]

来源:力扣(LeetCode)👈

??2、思路:

题目难点在于括号内嵌套括号,需要从内向外生成与拼接字符串,这与栈的先入后出特性对应。

  • 定义num存放解码出来的倍数,st存放num临时字符串的结果。遍历字符串s中每个字符c;
    • c为数字时,将字符转换为数值,赋给num
    • c为字母时,在res后面添加c
    • c[时,将倍数numres入栈,然后分别置空置0(进入新的[,需要重新开始记录)
    • c]时,将倍数numres出栈,进行拼接。

复杂度分析
?时间复杂度 O(N) :一次遍历s
🏠空间复杂度 O(N) :辅助栈最大需要线性空间。

🔑3、代码:

	class Solution {
	public:
	    string decodeString(string s) {
	        stack<pair<int, string>> st;
	        int num = 0;
	        string res="";
	        for(auto c : s){
	            if(c >= '0' && c <= '9'){ //整数取值,0~300
	                num *= 10;
	                num += (c - '0');    
	                //num = num * 10 + (c - '0');            
	            } //num记录下数字
	            else if(c == '['){ //把倍数和之前的res存起来
	                st.emplace(make_pair(num, res));
	                num = 0;
	                res = "";
	            }
	            else if(c == ']'){ //遇到]出栈数字和字符串,组装
	                int n = st.top().first;
	                string a = st.top().second;
	                st.pop();
	                for(int i=0;i<n;i++) a += res;
	                res = a;
	            }
	            else res += c;
	        }
	        return res;
	    }
	};

文章来源:https://blog.csdn.net/qq_45087381/article/details/135626964
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。