Problem overview
The method decompress receives a compressed string and returns the list of full paths it stands for. In the compressed form, a pair of braces holds a comma-separated list of alternatives, and those alternatives can themselves contain braces. Text next to a brace group is concatenated with each of its alternatives. A comma outside every brace separates independent paths.
Two small cases show the rules. a{b,c} means ab and ac. {a,b}x{c,d} means every combination of one choice from each group around the x: axc, axd, bxc and bxd. For my_{first,second}_folder/{a,b}{.js,.py} the result has eight paths, from my_first_folder/a.js to my_second_folder/b.py. The order of the result doesn't matter.
Approach: one recursive call per brace group
A nested format calls for recursion. Whenever the scan meets {, everything up to the matching } is a smaller instance of the same problem: a comma-separated list that may contain more braces. So the plan is a function that scans a list and returns its paths, and that calls itself on every {.
Within one list, the function keeps two arrays:
stringsholds the partial paths of the item being built since the last comma. It starts as[""], one empty string, so the first characters have something to attach to.currentLevelholds the finished paths of earlier items in this list.
Each character is handled by its kind. An ordinary letter is appended to every string in strings. A , moves strings into currentLevel and starts a fresh [""]. A { triggers a recursive call that returns the alternatives inside, and every string in strings is then paired with every alternative. A } ends the current call.
The recursive calls must carry on scanning where the previous one stopped, so the position can't be a local variable, which would restart at 0 in each call. It lives on the object as this.index, shared by all the calls.
Step by step
- Delegate.
decompressreturnsthis.parsePaths(input). Methods of the same class are called throughthis. - Declare
parsePathswith aninputparameter of typestringand the return typestring[]. - Create
currentLevelwithletas an emptystring[]. It is reassigned later, so it can't beconst. - Create
stringswithlet, starting as[""]. - Add the shared position. Declare the property
index: number;as the first line of the class, since TypeScript requires class properties to be declared, and set it to 0 in theconstructor. - Loop while
this.index < input.length. - Handle
{. Advancethis.indexso the recursive call starts after the brace. CallparsePathsand store the result innextLevel. Combine it withstringsusing a helper,concatAllPairs, and store the result back instrings. When the call returns,this.indexpoints at the}that closed the group. - Handle
}.breakout of the loop and give control back to the caller. - Handle
,. SetcurrentLevelto a new array that spreadscurrentLeveland thenstrings, and resetstringsto[""]. - Handle any other character. A classic
forloop appendsinput[this.index]to each element ofstrings. Strings are immutable, so each array slot is replaced with the longer string. - Advance with
this.index++below all branches. After a nested call, this is also what steps over the}. - Flush the last item. After the loop, spread
stringsintocurrentLevelonce more, because the final item has no comma after it, then returncurrentLevel. - Write
concatAllPairswith twostring[]parameters,firstandsecond. Two nestedfor...ofloops, withfirstPartandsecondPart, pushfirstPart + secondParttoresult, which is then returned.
The solution in TypeScript
class Solution {
index: number;
concatAllPairs(first: string[], second: string[]): string[] {
let result: string[] = [];
for (const firstPart of first) {
for (const secondPart of second) {
result.push(firstPart + secondPart);
}
}
return result;
}
constructor() {
this.index = 0;
}
parsePaths(input: string): string[] {
let currentLevel: string[] = [];
let strings: string[] = [""];
while (this.index < input.length) {
if (input[this.index] == "{") {
this.index++;
let nextLevel: string[] = this.parsePaths(input);
strings = this.concatAllPairs(strings, nextLevel);
} else if (input[this.index] == "}") {
break;
} else if (input[this.index] == ",") {
currentLevel = [...currentLevel, ...strings];
strings = [""];
} else {
for (let i = 0; i < strings.length; ++i) {
strings[i] += input[this.index];
}
}
this.index++;
}
currentLevel = [...currentLevel, ...strings];
return currentLevel;
}
decompress(input: string): string[] {
return this.parsePaths(input);
}
}
Here is how a{b,c} runs. The letter a makes strings equal to ["a"]. At { the index moves on and the recursive call scans b,c}. It builds ["b"], hits the comma and moves it into currentLevel, builds ["c"], stops at } and returns ["b", "c"]. Back in the first call, concatAllPairs(["a"], ["b", "c"]) gives ["ab", "ac"], and this.index++ steps over the }.
TypeScript details worth knowing:
- The property declaration.
index: number;is a type declaration; the constructor is what gives the property its starting value. Annotations likestring[]are erased when the code is compiled to JavaScript. - Spread.
[...currentLevel, ...strings]builds a new array holding the elements of both. It copies, so later changes tostringsdon't leak intocurrentLevel. - String indexing.
input[this.index]is a one-character string, which is why it can be compared with"{"and appended with+=. ==versus===. The code uses==. Between two strings it behaves like===, but===is the safer habit because it never converts types.- One object, one scan. The position is never reset, so each
Solutionobject can parse one input. Callingdecompressa second time on the same object starts at the old position: after"a,b"returned["a", "b"], a second call with the same text returns[""]. Create a newSolutionfor each input.
Complexity
The input is read one character at a time, but the cost is set by the output, not the input length. Every combination of alternatives becomes its own string, and every character in the input is appended to each partial path in progress. Two groups of 10 alternatives next to each other produce 100 paths, whatever the code looks like, so no solution can be faster than the size of its output. Extra space is the output plus a recursion depth equal to the deepest nesting of braces.
Edge cases and common mistakes
- No braces.
"README.md"returns["README.md"], and"a,b"returns["a", "b"]. - Empty input. The loop never runs, and the method returns
[""], a list with one empty path. - Nested groups.
a{b,{c,d}e}fgivesabf,acefandadef. The inner group{c,d}eis one alternative of the outer group. - Brace groups side by side.
{a,b}{c,d}gives four paths becausestringsis combined with each new group rather than replaced. - Forgetting the start value
[""]. With an emptystrings, there is nothing to append the first letter to, and the combining loops produce nothing. - Skipping the final flush. Without the last spread after the loop, the final item is lost, because no comma follows it.
- Not advancing the index before recursing. The recursive call would start on the
{itself and recurse forever. - Local position. A position stored in a local variable restarts at 0 in every call, so nested groups would be scanned twice or never.
Testing
"ab,ac"gives["ab", "ac"]."a{b,c}"gives["ab", "ac"]."{a,b}{c,d}"gives["ac", "ad", "bc", "bd"]."resources/{js/{app.js,comp/{a.js,b.js},boot.js}},README.md"gives["resources/js/app.js", "resources/js/comp/a.js", "resources/js/comp/b.js", "resources/js/boot.js", "README.md"], which holds the same five paths as the lesson's example in a different order.