本文主要是介绍LeetCode394. Decode String字符串解码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
394. Decode String
题意：
Given an encoded string, return its 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].
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Example 4:
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
例子分析
char-》int是c-'0',注意是将谁单引号！！！！！！！！！图片中的char到int的转换是错误的。
分析要点：
1.因为涉及到括号匹配问题，所以要用到栈（数字栈和字母栈），此时联想到四则运算中运用到栈（运算符栈和数字栈）。在此题中的数字栈就相当于四则运算中的运算符栈，因为都是根据栈中的内容的表示对对象进行某种操作。
2.题目中多次用到字符的拼接，这时候最好不要直接用str=str1+str2这种，因为底层涉及到字符串的复制，会产生多个字符串对象（str、str1、str2），所以最好是用StringBuilder。
3.因为用到StringBuilder，所以要用new分配内存，注意开头和结尾处String和StringBuider之间要进行转换。
复杂度
1.时间复杂度O(n)
2.空间复杂度O(n)
代码：
Python
class Solution:def decodeString(self, s: str) -> str:multi=0res=''multiStack=[]resStack=[]for c in s:if c.isdigit():multi=multi*10+int(c)elif c=='[':multiStack.append(multi)multi=0resStack.append(res)res=''elif c==']':cur_multi=multiStack.pop()pre_res=resStack.pop()res=pre_res+cur_multi*reselse:res=res+creturn res
Java
class Solution {public String decodeString(String s) {int multi=0;StringBuilder res=new StringBuilder();//存放结果//创建两个栈：数字栈和字母栈LinkedList<Integer> multiStack=new LinkedList<>();LinkedList<String> resStack=new LinkedList<>();for(char c:s.toCharArray()){if(c>='0'&&c<='9'){//当遇到的是数字multi=multi*10+(c-'0');//当数字是多位数；字符转换成数字：c-'0'}else if(c=='['){//当遇到的是左括号：数字栈和字母栈都入栈，并且将multi和res清一下multiStack.addLast(multi);multi=0;resStack.addLast(res.toString());res=new StringBuilder(); }else if(c==']'){//当遇到的是右括号,将数字栈和字母栈都出栈，构造pre_res=resStack+multiStack*res；并更新resint cur_multi=multiStack.removeLast();//栈：先进后出StringBuilder tmp=new StringBuilder();for(int i=0;i<cur_multi;++i){tmp.append(res);}res=new StringBuilder(resStack.removeLast()+tmp);}else{//当遇到的是字母res.append(c); }}return res.toString();}
}
这篇关于LeetCode394. Decode String字符串解码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
