Problem overview
Decompress(input) receives a compressed list of paths, a "token list", and returns the original list of strings. Commas separate alternatives, and braces group them: a{b,c} stands for ab and ac, and a group can sit anywhere in a string, be followed by more text, and contain further groups. Several groups in a row multiply: {a,b}{c,d} gives ac, ad, bc and bd. The result may come back in any order.
For "my_{first,second}_folder/{a,b}{.js,.py}", the first group has 2 options and the other two groups together have 2 * 2 = 4, so the result has 8 paths, from my_first_folder/a.js to my_second_folder/b.py.
Approach: one recursive call per pair of braces
The grammar is recursive: the inside of a pair of braces is itself a token list. That suggests a function, parsePaths, that reads one token list and returns all its expansions. When it meets {, it calls itself to expand the inside, and when it meets }, it stops and hands control back.
The function keeps two lists while it scans:
strings: the partial paths for the current comma-separated alternative. It starts as[""], a single empty string, so that the first letters have something to attach to.currentLevel: the finished paths of this nesting level, collected when a comma or the end of the level is reached.
Each character is handled in one of four ways. A letter is appended to every string in strings. A { expands the nested list and multiplies it with strings. A , moves strings into currentLevel and starts again from [""]. A } ends the level.
Trace a{b,c}. At the top level, strings becomes ["a"]. At {, a nested call starts with [""]: b gives ["b"], the comma moves it into the nested currentLevel, c gives ["c"], and } stops the call, which returns ["b", "c"]. Back at the top, every string in ["a"] is paired with every string in ["b", "c"], which gives ["ab", "ac"].
Step by step
- Delegate.
Decompressjust returnsparsePaths(input). Inside a class, one method can call another by its name alone. - Declare
parsePaths(string input), returning aList<string>. It has no access modifier, so it is private, which suits a helper. - Create
currentLevel, an empty list for this level's finished paths. - Create
stringswith the collection initializer{ "" }, which adds one empty string right after the list is constructed. - Keep the position in a field. A recursive call must continue exactly where the previous one stopped, but a local variable restarts at 0 in every call. An
int indexfield is shared by all calls on the same object. The constructor sets it to 0. - Loop while
index < input.Length. - On
'{': incrementindexso the nested call starts after the brace, callparsePaths(input)and store the result innextLevel. When the call returns,indexpoints at the'}'that ended it. - Multiply. Replace
stringswithconcatAllPairs(strings, nextLevel): every prefix in progress must pair with every nested option. - On
'}':break. The nested list is finished, and control returns to the caller. - On
',': add everything instringstocurrentLevelwithAddRange, then resetstringsto a fresh[""]. - Otherwise it's a character of a path. Append it to every string in
stringswith aforloop, writing each result back:strings[i] = strings[i] + input[index]. Strings are immutable, so the new string must be stored in the list. - Advance. Increment
indexat the bottom of the loop. After a nested call, this is also what steps over the'}'that ended it. - Finish the level. After the loop,
stringsmay hold paths that never met a comma, so add them tocurrentLeveland return it. - Write
concatAllPairs(first, second). Two nestedforeachloops addfirstPart + secondPartto a result list for every pair, so the result hasfirst.Count * second.Countstrings.
The solution in C#
class Solution {
List<string> concatAllPairs(List<string> first, List<string> second) {
List<string> result = new List<string>();
foreach (string firstPart in first) {
foreach (string secondPart in second) {
result.Add(firstPart + secondPart);
}
}
return result;
}
int index;
public Solution() {
index = 0;
}
List<string> parsePaths(string input) {
List<string> currentLevel = new List<string>();
List<string> strings = new List<string> { "" };
while (index < input.Length) {
if (input[index] == '{') {
++index;
List<string> nextLevel = parsePaths(input);
strings = concatAllPairs(strings, nextLevel);
} else if (input[index] == '}') {
break;
} else if (input[index] == ',') {
currentLevel.AddRange(strings);
strings = new List<string> { "" };
} else {
for (int i = 0; i < strings.Count; ++i) {
strings[i] = strings[i] + input[index];
}
}
index++;
}
currentLevel.AddRange(strings);
return currentLevel;
}
public List<string> Decompress(string input) {
return parsePaths(input);
}
}C# details worth knowing
new List<string> { "" }is a collection initializer: it calls the constructor and thenAdd("").strings[i] = strings[i] + input[index];works becausestring + charproduces a new string with the character appended. AListcan be both read and assigned through brackets.- Comparing
input[index] == '{'compares twocharvalues, so it uses single quotes. Double quotes would make it a string, which doesn't compare with achar. index++as a statement and++indexdo the same thing here; only the old and new values differ when used inside an expression.- The constructor has the class's name and no return type. A field of type
intalready starts at 0, so settingindex = 0only makes the intent explicit.
Complexity
The output can be much larger than the input: every group of k options multiplies the number of paths by k, so three groups of two options give 8 paths, and ten of them would give 1,024. The running time is therefore dominated by the size of the result. Each character of the input is visited once, but a letter is appended to every string in progress, and each append copies a string. Memory is the size of the result plus the recursion depth, which equals the nesting depth of the braces.
Edge cases and common mistakes
- No braces and no commas.
"abc"returns["abc"]: the loop only appends letters, and the finalAddRangemoves the result intocurrentLevel. - Forgetting the final
AddRange. The last alternative of every level ends at a}or at the end of the input, not at a comma, so without it that alternative is lost. - A local instead of a field for the position. Every recursive call would restart at 0, so a nested call could never continue where the outer one stopped.
- Starting
stringsas an empty list. A letter would have nothing to be appended to, and the result would be empty. - Reusing one
Solutionobject. The fieldindexis left at the end of the input after a call. A second call toDecompresson the same object starts at the end and returns an empty list. Create a new object per input, or resetindexat the start ofDecompress.
Testing
ab,ac -> ab, ac
a{b,c} -> ab, ac
axc,axd,bxc,bxd -> axc, axd, bxc, bxd
README.md,resources/js/{app,boot,comp/{a,b}}.js
-> README.md, resources/js/app.js, resources/js/boot.js,
resources/js/comp/a.js, resources/js/comp/b.js