394. String decoding
https://leetcode-cn.com/problems/decode-string/
- 394. String decoding
- Question description
- Method 1: Recursive
- Ideas
- Complexity analysis
- code
- Method 2: Loop + Stack
- Illustration
- Complexity analysis
- code
Title description
Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], which means that the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer. You can assume that the input string is always valid; there are no extra spaces in the input string, and the input square brackets are always well-formed. Furthermore, you can think of the original data as containing no numbers, and all the numbers only represent the number of repetitions k , for example there will be no input like 3a or 2[4] . Example: s = "3[a]2[bc]", returns "aaabcbc". s = "3[a2[c]]", returns "accaccacc". s = "2[abc]3[cd]ef", returns "abcabccdcdcdef". Source: LeetCode Link: https://leetcode-cn.com/problems/decode-string The copyright belongs to Lingkou Network. For commercial reprinting, please contact the official authorizer. For non-commercial reprinting, please indicate the source.
Method 1: Recursion
Ideas
n[string] means parsing the content in the [] template, and then repeating n times to get a string concatenated by n strings.
According to the meaning of the question, [] can also be nested inside [], such as n[m[string]]. In this case, we have to parse the innermost template first, repeat m times, and then use the result of m * string as the parsed content of the outer template, and repeat n times.
If there are more nesting levels, we have to find the innermost [] first, just like an onion, peeling it off layer by layer, and then layer by layer from the inside to the outside. Analyzing and splicing layer by layer. This description easily brings to mind recursion.
Take a look at the code comments.
Complexity analysis
- time complexity:
O
(
S
)
O(S)
O(S), S is the length of the parsed string.
- Space complexity:
O
(
S
)
O(S)
O(S), S is the length of the parsed string and the recursive stack space.
Code
const type = {<!-- -->
isAlpha: s => /[a-z]/i.test(s),
isDigit: s => /[0-9]/.test(s),
isOpenParen: s => s === '[',
isCloseParen: s => s === ']',
};
/**
* @param {string} s
* @return {string}
*/
var decodeString = function (s, i = 0) {<!-- -->
// Traverse the string starting from i
let decoded = ''; // Decrypt string
let cnt = ''; // Accumulated times
while (i < s.length) {<!-- -->
if (type.isAlpha(s[i])) {<!-- -->
// Ordinary characters, directly spliced to decoded
decoded + = s[i];
i + + ;
} else if (type.isDigit(s[i])) {<!-- -->
// Number, spliced to cnt
cnt + = s[i];
i + + ;
} else if (type.isOpenParen(s[i])) {<!-- -->
//When encountering an open bracket, repeat the string in the bracket cnt times, and then splice it into decoded
// But there may be nested brackets within the brackets, so recursive processing is required
// We need to take two things from the recursion, 1. The parsed pattern within the brackets, 2. The subscript of the right bracket corresponding to the open bracket. The next time the string is traversed, it will start from this subscript + 1
const [pattern, nextIndex] = decodeString(s, i + 1);
// Repeat cnt times to splice into decoded
decoded + = pattern.repeat(Number(cnt));
cnt = '';
i = nextIndex;
continue;
} else if (type.isCloseParen(s[i])) {<!-- -->
// When closing brackets are encountered, it means that the pattern within the brackets has been parsed.
//The recursion ends and returns what we need: 1. The parsed string, 2. The parsed character subscript
return [decoded, i + 1];
}
}
return decoded;
};
C++Code
class Solution {<!-- -->
private:
int ptr_ = 0;
public:
string decodeString(string s) {<!-- -->
string decoded_str = "";
string repeat_times = "";
int i = ptr_;
while (i < s.length()) {<!-- -->
if (isalpha(s[i])) {<!-- -->
decoded_str + = s[i];
i + + ;
} else if (isdigit(s[i])) {<!-- -->
repeat_times + = s[i];
i + + ;
} else if (s.compare(i, 1, "[") == 0) {<!-- -->
ptr_ = i + 1;
string pattern = decodeString(s);
i = ptr_;
int times = stoi(repeat_times);
for (int t = 0; t < times; t + + ) {<!-- -->
decoded_str + = pattern;
}
repeat_times = "";
} else if (s.compare(i, 1, "]") == 0) {<!-- -->
ptr_ = i + 1;
return decoded_str;
}
}
return decoded_str;
}
};
Method 2: Loop + Stack
Problems that can be solved recursively can also be solved using loops.
Here I used the regular /[a-zA-Z] + |[0-9] + |\[|\]/ and exec() methods to Iterate over strings and split them into token, for example, lz3[ab2[c]] will be split into lz, 3, [, ab, 2, [, c, ], ].
- When encountering a letter block (
lz) or a number, push it onto the stack; - When
[is encountered, it is pushed onto the stack to indicate that it is currently entering a template for parsing; - When encountering
], it means that the current template has been traversed and we can start parsing. Start popping the stack and splicing the popped letter blocks together. When[is popped out of the stack, it means that the current template parsing is completed. Continue to pop an element out of the stack. This element is the number of times the current template will be repeated. Then push “letter block * times” onto the stack. The reason why it is pushed into the stack is that templates can be nested, and the outer layer of the current template can still be a template, so we have to put the result back and continue to parse the outer template.
Illustration
Complexity analysis
- time complexity:
O
(
S
)
O(S)
O(S), S is the length of the parsed string.
- Space complexity:
O
(
S
)
O(S)
O(S), S is the length of the parsed string.
Code
/**
* @param {string} s
* @return {string}
*/
var decodeString = function (s) {<!-- -->
const reg = /[a-zA-Z] + |[0-9] + |\[|\]/g;
const stack = [];
const peek = () => stack[stack.length - 1]; // p.s. Improper stack
while (reg.lastIndex < s.length) {<!-- -->
let token = reg.exec(s)[0];
if (token !== ']') {<!-- -->
//Numbers, letters, and left brackets are all pushed onto the stack
stack.push(token);
} else {<!-- -->
//Start popping the stack when encountering the right parenthesis
let str = '';
// [] The middle one is the pattern to be repeated. Pop them all off the stack and splice them together.
while (peek() !== '[') {<!-- -->
str = stack.pop() + str;
}
// throw away the left bracket
stack.pop();
//The thing before the left bracket must be the number of times the pattern is repeated.
const num = + stack.pop();
// Put the copied string back on the stack as part of the outer [] pattern
stack.push(str.repeat(num));
}
}
return stack.join('');
};
Summary
The above is all the content of this article. I hope it can be helpful to you and solve the problem of string decoding.
If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!
It has been completed, please continue to pay attention. See you next time~