当前位置:网站首页>LeetCode:394. String decoding
LeetCode:394. String decoding
2022-07-06 08:50:00 【Bertil】
Given an encoded string , Returns the decoded string .
The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .
You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements .
Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of .
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"
Tips :
- 1 <= s.length <= 30
- s By lowercase letters 、 Numbers and square brackets ‘[]’ form
- s Guarantee is a It works The input of .
- s The value range of all integers in is [1, 300]
Their thinking
1. From inside to outside , Solve layer by layer [ ], Need to keep memory of characters , So use the stack
2. Time to enter the stack : encounter [ It means solving internal problems first , External numbers and letters go to the stack and wait
- When you meet [, The number that has been scanned is “ Multiple ”, Stack temporarily
- When you meet [, The scanned letters are also stacked and waiting , Wait until the decoding in brackets is finished , Can participate in the construction of strings together
3. Time to get out of the stack : encounter ] It means that the scanning of the inner layer is finished , Top element of stack ( I met you recently “ Multiple ” And letters ) You can get out of the stack , Jointly participate in the construction of substrings
Code
/** * @param {string} s * @return {string} */
var decodeString = function(s) {
let numStack = []; // Stack of multiples
let strStack = []; // save To be spliced str The stack
let num = 0; // Temporary multiple
let result = ''; // Temporary string
for (const char of s) {
// Character by character scanning
if (!isNaN(char)) {
// When it comes to numbers
num = num * 10 + Number(char); // Calculate multiple
} else if (char == '[') {
// encounter [
strStack.push(result); // result String into stack
result = '';
numStack.push(num); // Multiple num Enter the stack and wait
num = 0;
} else if (char == ']') {
// encounter ], The stack of two stacks comes out of the stack
let repeatTimes = numStack.pop(); // Number of copies obtained
result = strStack.pop() + result.repeat(repeatTimes); // Build substrings
} else {
result += char; // Letters encountered , Append to result strand
}
}
return result;
};
边栏推荐
- C language double pointer -- classic question type
- @Jsonbackreference and @jsonmanagedreference (solve infinite recursion caused by bidirectional references in objects)
- Pytorch view tensor memory size
- LeetCode:39. 组合总和
- What are the common processes of software stress testing? Professional software test reports issued by companies to share
- Philosophical enlightenment from single point to distributed
- marathon-envs项目环境配置(强化学习模仿参考动作)
- Super efficient! The secret of swagger Yapi
- LeetCode:394. 字符串解码
- What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
猜你喜欢
C語言雙指針——經典題型
软件卸载时遇到trying to use is on a network resource that is unavailable
TCP/IP协议
Visual implementation and inspection of visdom
Marathon envs project environment configuration (strengthen learning and imitate reference actions)
pytorch训练好的模型在加载和保存过程中的问题
704 binary search
企微服务商平台收费接口对接教程
sublime text中conda环境中plt.show无法弹出显示图片的问题
Excellent software testers have these abilities
随机推荐
torch建立的网络模型使用torchviz显示
Crash problem of Chrome browser
TP-LINK 企业路由器 PPTP 配置
Process of obtaining the electronic version of academic qualifications of xuexin.com
LeetCode:41. 缺失的第一个正数
Swagger setting field required is mandatory
Current situation and trend of character animation
Using pkgbuild:: find in R language_ Rtools check whether rtools is available and use sys The which function checks whether make exists, installs it if not, and binds R and rtools with the writelines
To effectively improve the quality of software products, find a third-party software evaluation organization
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
JS pure function
Roguelike game into crack the hardest hit areas, how to break the bureau?
opencv+dlib实现给蒙娜丽莎“配”眼镜
Restful API design specification
Generator parameters incoming parameters
LeetCode:剑指 Offer 48. 最长不含重复字符的子字符串
LeetCode:剑指 Offer 04. 二维数组中的查找
超高效!Swagger-Yapi的秘密
UML diagram memory skills
LeetCode:39. 组合总和