Problem overview
The function decompress receives a compressed Token List as a String and returns the list of paths it stands for, as a Vec<String>. In a token list, commas separate alternatives, and a pair of braces groups a nested token list. Whatever stands next to a group is joined to each of the group's alternatives, so a{b,c} means ab and ac, and {a,b}x{c,d} means axc, axd, bxc and bxd.
The input my_{first,second}_folder/{a,b}{.js,.py} expands to eight paths, from my_first_folder/a.js to my_second_folder/b.py: two choices for the first group, two for the second and two for the third. The result may come back in any order.
Approach: recursion on the braces
The nesting is the key. Everything between a { and its matching } is itself a token list, so it can be decompressed by the same logic, and the result is a list of strings that gets joined onto what came before. That calls for recursion, with one function that reads a token list until it hits the } that closes it, or the end of the input.
Each call keeps two lists:
stringsholds the paths being built since the last comma. It begins with one empty string. Each plain character is appended to every string in the list.current_levelholds the finished alternatives of this level. A comma moves everything fromstringsinto it and resetsstringsto one empty string.
When the call sees a {, it recurses to get the nested alternatives and combines them with strings by pairing every string with every alternative. The result replaces strings.
All the calls read the same input from one shared position. A call that finishes stops with the position on its }, and the caller moves past it. That is why the position is passed as a mutable reference, so every level advances the same counter.
For x{a,b}y: strings becomes ["x"] after the first character. The brace starts a recursive call, which builds ["a"], moves it into its current_level at the comma, builds ["b"] and returns ["a", "b"] at the closing brace. Pairing gives ["xa", "xb"], and the last character turns these into ["xay", "xby"].
Step by step
- Delegate in
decompress. Make the call to the recursive helperparse_paths_innerthe last expression ofdecompress. It receives the characters and a mutable reference to the position. - Declare the helper with a
&[char]and a&mut usizeand aVec<String>result. - Create
current_levelas an empty vector for the finished paths. - Create
stringswith a single empty string, so the first character has something to be appended to. - Prepare the input in
decompress: collect the input into aVec<char>namedcharsand createindex, set to 0. - Walk the characters with a
whileloop that runs while*indexis less thanchars.len(), storing the current character inc. - On
{, move past the brace, call the helper recursively and combinestringswith the returnednext_levelusingconcat_all_pairs. - On
}, break: the nested list is finished and control goes back to the caller. - On
,, move the finished paths intocurrent_leveland start over with one empty string. - Otherwise, append the character to every string in
strings. - Advance the position after the branches. After a nested call, this also steps past the
}that ended it. - Flush the last paths. After the loop,
stringsmay hold paths that never met a comma, so move them intocurrent_leveland return it. - Write
concat_all_pairs, which takes two slices of strings and returns every string of the first joined with every string of the second.
The solution in Rust
impl Solution {
fn concat_all_pairs(first: &[String], second: &[String]) -> Vec<String> {
let mut result = Vec::new();
for f in first {
for s in second {
result.push(format!("{}{}", f, s));
}
}
result
}
fn parse_paths_inner(chars: &[char], index: &mut usize) -> Vec<String> {
let mut current_level: Vec<String> = Vec::new();
let mut strings: Vec<String> = vec!["".to_string()];
while *index < chars.len() {
let c = chars[*index];
if c == '{' {
*index += 1;
let next_level = Self::parse_paths_inner(chars, index);
strings = Self::concat_all_pairs(&strings, &next_level);
} else if c == '}' {
break;
} else if c == ',' {
current_level.extend(strings.drain(..));
strings = vec!["".to_string()];
} else {
for s in &mut strings {
s.push(c);
}
}
*index += 1;
}
current_level.extend(strings.drain(..));
current_level
}
fn decompress(input: String) -> Vec<String> {
let chars: Vec<char> = input.chars().collect();
let mut index = 0;
Self::parse_paths_inner(&chars, &mut index)
}
}
Rust details worth a closer look:
- Characters, not bytes. A Rust
Stringcan't be indexed by position, sodecompresscollectsinput.chars()into aVec<char>. The helper takes&[char], and a reference to the vector converts to the slice automatically. - A shared position.
index: &mut usizeis a mutable reference, so reading it is*indexand changing it is*index += 1. Indecompress,let mut index = 0;becomes ausizebecause&mut indexis passed to the helper. Inside the recursive call,indexis passed on without an extra&mut, because it already is a mutable reference. Rust reborrows it for the call, so the code can keep usingindexafterwards. - Moving strings between vectors.
current_level.extend(strings.drain(..))removes every element fromstringsand appends it tocurrent_levelwithout cloning.drainleavesstringsempty, which is why the comma branch assigns a freshvec!["".to_string()]right after. - Mutating in place.
for s in &mut stringsgives a mutable reference to eachString, ands.push(c)appends onecharto it. - Building the product.
format!("{}{}", f, s)creates a newStringfrom the two borrowed ones.concat_all_pairsborrows both lists, and the callSelf::concat_all_pairs(&strings, &next_level)assigns the result back tostrings.Vec::new()needs no type annotation there, because the pushes tell the compiler it holdsStringvalues. - Associated functions. The helpers have no
self, so they are called asSelf::parse_paths_innerandSelf::concat_all_pairs.
Complexity
The cost depends on the output, not only on the input length. Let the result contain P paths of length up to M.
Time: proportional to the size of the output, O(P · M), up to the extra copying of intermediate lists. Every plain character is appended to each string being built, and every group pairs lists with a copy of each string. The result can be exponentially larger than the input: {a,b}{a,b}{a,b} has 15 characters and expands to 8 paths, and each extra group doubles it. No algorithm can do better than the size of what it must return.
Space: O(P · M). The result is held in memory, and the recursion depth equals the nesting depth of the braces.
Edge cases and common mistakes
- No braces or commas.
"x"returns["x"], because the final flush moves the single string into the result. - Commas at the top level.
"a,b{c,d}"returns["a", "bc", "bd"]. The comma separates two alternatives, and onlybis joined with the group. - Adjacent groups multiply.
{a,b}x{c,d}gives four paths, anda{b,c}dgives["abd", "acd"]. - An empty alternative.
x{,a}gives["x", "xa"], because the empty string before the comma is a valid alternative. - Forgetting the final flush. Paths that never meet a comma stay in
stringsand are lost. Every input without a trailing comma depends on this step. - Forgetting to reset
stringsat a comma. The next alternative would be appended onto the previous one's paths. - Not stepping past
}. The nested call stops with the position still on its}. The caller's increment at the bottom of its loop steps over it. Without that step, the caller would read the same}and end its own level too early. - Using a local position. If each call counted from zero, the nested call would re-read the input from the start. The position must be shared.
Testing
"ab,ac"gives["ab", "ac"]."a{b,c}d"gives["abd", "acd"]."{a,b}x{c,d}"gives["axc", "axd", "bxc", "bxd"]."resources/{js/{app.js,comp/{a.js,b.js},boot.js}},README.md"gives the five paths from the statement, in this order:resources/js/app.js,resources/js/comp/a.js,resources/js/comp/b.js,resources/js/boot.js,README.md.
