Problem overview
The function decode_string receives an encoded string s and returns the decoded one. The rule is k[encoded_string]: the text inside the square brackets is repeated exactly k times. Groups can be nested, and plain letters can appear anywhere between them. The input is always valid, and digits appear only as repeat counts, so inputs such as 3a or 2[4] don't occur.
For "3[a]2[bc]" the answer is "aaabcbc". For "3[a2[c]]" the inner group 2[c] becomes cc, so the outer group repeats acc three times and gives "accaccacc". For "2[abc]3[cd]ef" the answer is "abcabccdcdcdef", with the trailing ef copied as it is.
Approach: decode a group when its bracket closes
A group can only be expanded once everything inside it is decoded. In a nested string that means the innermost group comes first, and the innermost group is always the one opened most recently. That is the behaviour of a stack.
The solution keeps one stack of strings, and its entries are of two kinds:
- a count entry, which holds only digits, such as
"23"; - a text entry, which collects decoded letters.
Every [ pushes a new, empty text entry, and it always sits on top of the count that was read just before it. Letters are appended to the top entry. Digits either start a new count entry or extend the one on top. A ] pops the text, pops the count under it, repeats the text and appends the result to whatever is now on top, which is the text of the enclosing level.
For "3[a2[c]]" the stack goes through these states:
after "3[" : ["3", ""]
after "a" : ["3", "a"]
after "2[" : ["3", "a", "2", ""]
after "c" : ["3", "a", "2", "c"]
after "]" : ["3", "acc"]
after "]" : ["accaccacc"]The first ] pops "c" and the count "2", and appends "cc" to the "a" below. The second pops "acc" and "3", leaving the stack with nothing in it, so the result becomes the single remaining entry.
Step by step
- Create the stack
stackas an emptyVec<String>. - Loop over the characters of
swithchars(), naming the variablec, and give each kind of character its own branch. - Handle
[. Push an emptyStringto start the buffer for the bracketed text. - Handle letters in a branch that tests
c.is_ascii_alphabetic(). If the stack is empty, as it is for letters before any bracket, push an empty buffer first. Then append the letter to the last entry throughlast_mut(). - Handle digits in a branch that tests
c.is_ascii_digit(). Look at a copy of the top entry, or an empty string when the stack is empty. If that entry is empty or contains something other than digits, a new count begins, so pushc.to_string()as a new entry. Otherwise the top is a count in progress, so append the digit to it. This is how23ends up in one entry instead of two. - Handle
]in the finalelse. Pop the text intocurr_str, pop the count andparseit into ausizenamedcurr_num, and build the repeated text withcurr_str.repeat(curr_num). - Put the result back. If the stack is empty, the group was at the top level, so push the repeated text as a new entry. Otherwise append it to the last entry, which is the enclosing buffer.
- Return the one entry left on the stack.
pop()gives anOption, andunwrap_or_default()turnsNoneinto an empty string.
The solution in Rust
impl Solution {
fn decode_string(s: String) -> String {
let mut stack: Vec<String> = Vec::new();
for c in s.chars() {
if c == '[' {
stack.push(String::new());
} else if c.is_ascii_alphabetic() {
if stack.is_empty() {
stack.push(String::new());
}
stack.last_mut().unwrap().push(c);
} else if c.is_ascii_digit() {
let top = stack.last().cloned().unwrap_or_default();
if top.is_empty() || !top.chars().all(|ch| ch.is_ascii_digit()) {
stack.push(c.to_string());
} else {
stack.last_mut().unwrap().push(c);
}
} else {
let curr_str = stack.pop().unwrap();
let curr_num: usize = stack.pop().unwrap().parse().unwrap();
let repeated = curr_str.repeat(curr_num);
if stack.is_empty() {
stack.push(repeated);
} else {
*stack.last_mut().unwrap() += &repeated;
}
}
}
stack.pop().unwrap_or_default()
}
}
Rust details worth knowing:
- Cloning the top entry.
stack.last().cloned().unwrap_or_default()turns anOption<&String>into an ownedString, or an empty one if the stack is empty. Because the copy is owned, the borrow ofstackends at once, and the next lines can callpushorlast_mutwithout a borrow conflict. The cost is a copy of the top entry for every digit. allon an empty string."".chars().all(|ch| ch.is_ascii_digit())istrue, since there is no character that fails the test. That is why the code checkstop.is_empty()separately. Without it, a digit that follows a[would be glued onto the empty text buffer instead of starting a new count.*stack.last_mut().unwrap() += &repeated.last_mut()givesOption<&mut String>, and the*reaches the string itself.String += &strappends in place, and&repeatedborrows the new string as a&str.- Parsing.
let curr_num: usize = ....parse().unwrap();uses the type annotation to pick the target type ofparse. It returns aResult, andunwrap()would panic on a non-number such as"x". Valid input only puts digits in count entries. Ausizeis whatstr::repeattakes. repeat."ab".repeat(3)is"ababab". It builds the whole result in one allocation.- The last
else. Letters, digits and[are matched by earlier branches, so for valid input the finalelseonly sees].
Complexity
Time: O(L × d) at worst, where L is the length of the decoded output and d is the nesting depth. Each character of the input is handled once, apart from the copy of the top entry made for every digit, which is tiny. The cost is in the repeat calls and appends: text inside nested groups is copied once at each level it passes through. Nested counts multiply, so the decoded text can be far longer than the input, and the lesson limits it to 100,000 characters. With an input of at most 30 characters the depth is small.
Space: O(L). The stack holds buffers whose total size is at most the decoded text so far.
Edge cases and common mistakes
- Multi-digit counts.
"12[x]"gives twelvexcharacters. If each digit started its own entry, the code would read the count as2. - Nested counts back to back.
"2[3[a]b]"givesaaabaaab. The3right after a[sees an empty top entry and starts a new count. - Letters before and after a group.
"ab2[c]d"givesabccd. The count2is a separate entry on top ofab, and the decodedccis appended toabwhen the group closes. - Two groups in a row.
"2[a]3[b]"givesaabbb. After the first group closes, the stack holds"aa", which contains letters, so the next digit3starts a new count. - No brackets at all.
"abc"returnsabc; the lazily created buffer collects the letters. - Treating a count as text. Without the digit test, a count that follows decoded text would be appended to that text. Keeping counts as their own all-digit entries is what keeps the two kinds apart.
Testing
"3[a]2[bc]"givesaaabcbc."3[a2[c]]"givesaccaccacc."2[abc]3[cd]ef"givesabcabccdcdcdef."2[a2[b]c]"givesabbcabbc."10[a]"gives tenacharacters.
