Problem overview
The method decompress receives a compressed list of paths as a string, input, and returns every path it stands for as a []string. The notation is made of three things:
- plain characters, which are copied as they are;
- a comma, which separates alternatives at the same level;
- braces, which group a nested list. A nested list is joined with whatever is written before and after it, once for every alternative inside.
So a{b,c} means ab and ac, and {a,b}x{c,d} means 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 pair of braces
A nested list is a smaller instance of the same problem: text with commas and possibly more braces inside. That makes recursion natural. A function that parses one level can handle a { by calling itself, and it returns when it meets the matching } or the end of the text.
Each level keeps two collections:
currentLevel, the finished alternatives, which are the strings completed by a comma or by the end of the level;strings, the alternatives being built since the last comma.
Plain characters are appended to every string in strings, because all the partial paths in progress share them. When a nested list comes back with its own alternatives, strings is replaced by every string in it paired with every alternative from the nested list. A comma moves strings into currentLevel and starts again with a single empty string.
The trace for a{b,c}:
- Start with
strings = [""]. The characteraturns it into["a"]. - The
{starts a recursive call. Inside it,bis built, the comma moves["b"]to the level's results, and thencis built. At the}the call returns["b", "c"]. - Back in the outer call, pairing
["a"]with["b", "c"]gives["ab", "ac"]. The end of the input appends it tocurrentLevel.
The recursive call must continue reading where the outer call stopped, and the outer call must continue after the } where the inner call stopped. So the reading position is shared: one index that all the calls move.
Step by step
- Write
decompressin terms of a helper,parsePaths(input), a method on*Solution, so it is called through the receivers. - Declare
parsePathswith the pointer receivers *Solution, takinginputand returning a[]string. - Create
currentLevelas an empty slice for the finished paths of this level. - Create
stringsholding one empty string. Without that starting element there would be nothing for the first characters to be appended to, and the pairing step would produce nothing. - Add the
indexfield toSolution. A local variable would restart at 0 in every recursive call. A field is shared by all calls, and Go starts it at 0. - Loop while
s.index < len(input). - On
{, move past it withs.index++, callparsePathsand keep the result asnextLevel, and replacestringswith the pairing ofstringsandnextLevel, using a helper namedconcatAllPairs. When the call returns,s.indexpoints at the}that ended it. - On
},break. This level is finished, and the caller will step past the brace. - On
,, append all ofstringstocurrentLeveland resetstringsto a slice with one empty string. - Otherwise, the character is part of a name: append it to every string in
strings. Indexing a string gives a byte, so it is converted withstring(input[s.index])first. - Advance
s.indexat the bottom of the loop. After a nested call, this step is also what moves past its closing brace. - After the loop, append what is left in
stringstocurrentLevel, because the last alternative of a level is never followed by a comma, and returncurrentLevel. - Write
concatAllPairs: create an emptyresult, loop overfirstand, inside it, oversecond, appendfirstPart+secondPartevery time, and returnresult.
The solution in Go
type Solution struct {
index int
}
func (s *Solution) concatAllPairs(first []string, second []string) []string {
result := []string{}
for _, firstPart := range first {
for _, secondPart := range second {
result = append(result, firstPart+secondPart)
}
}
return result
}
func (s *Solution) parsePaths(input string) []string {
currentLevel := []string{}
strings := []string{""}
for s.index < len(input) {
if input[s.index] == '{' {
s.index++
nextLevel := s.parsePaths(input)
strings = s.concatAllPairs(strings, nextLevel)
} else if input[s.index] == '}' {
break
} else if input[s.index] == ',' {
currentLevel = append(currentLevel, strings...)
strings = []string{""}
} else {
for i := 0; i < len(strings); i++ {
strings[i] += string(input[s.index])
}
}
s.index++
}
currentLevel = append(currentLevel, strings...)
return currentLevel
}
func (s *Solution) decompress(input string) []string {
return s.parsePaths(input)
}
The Go details worth knowing:
- Methods and pointer receivers. With
s *Solution, every method works on the same struct, so a change tos.indexin a deep recursive call is visible in the callers. A value receiver would receive a copy, and the position would not survive the call. - Bytes and strings.
input[s.index]is abyte, and it compares directly with a character literal such as'{'. Adding it to a string needs a conversion:string(input[s.index]). This works on bytes, which is right for the ASCII characters of file paths. A multi-byte character would be split into several bytes, and the conversion of a single byte would produce the wrong character. append(a, b...). The...after a slice passes its elements toappendone by one, so it adds all of them. Without it,appendwould expect a single string. The result must be assigned back.- Shadowing a package name.
stringsis also the name of a standard package. Declaring a variable with that name hides the package inside the method. That's harmless here because the package isn't used, but it is a habit to avoid in code that imports it. - Empty slice versus
nil.[]string{}and anilslice both work withappendandrange. The empty literal is used forresultandcurrentLevelso that a call with no output returns an empty slice rather thannil. strings[i] += ...changes the slice. Strings are immutable, but the slice elements are variables that can be reassigned. Each element gets a new, longer string.
Complexity
Let n be the length of input and m the number of paths in the result.
Time. The parser reads each character once, so the scanning itself is O(n). The expensive part is building the output. Pairing two lists creates one new string per pair, and appending a character touches every string being built. The total work is therefore proportional to the size of everything produced, about m times the average path length, plus the intermediate lists. Because the output can be much larger than the input, as with {a,b}{c,d}{e,f}, the cost is output-bound.
Space. The result takes O(m * length) memory. The recursion depth is the number of nested braces, at most n.
Edge cases and common mistakes
- No braces at all.
"README.md,docs"returns two paths. Each comma finishes one alternative. - A list in the middle of a name.
"resources/js/{app,boot,comp/{a,b}}.js"shows why the plain characters after a}matter:.jsis appended to every string produced by the group. - Two groups in a row.
{a,b}{.js,.py}pairs the results of the first group with the second, giving four strings. - Forgetting the last alternative. A level doesn't end with a comma. Without the final
appendafter the loop, the last alternative of every level would be lost. - Starting
stringsempty. With no element, pairing with a nested list gives nothing, because there are zero first parts to combine. - Not skipping the closing brace. The
s.index++at the bottom steps over the}that ended a nested call. If the brace were left in place, the outer call would see it and stop too. - Reusing a
Solution.indexis never reset, so a second call todecompresson the same value starts at the end of the previous input. It returns a slice holding one empty string. Create a newSolutionfor each input. - Unbalanced braces. A stray
}at the top level stops the parse early:"x,y}z"givesxandy, andzis never read. The problem only gives well-formed input.
Testing
"a{b,c}"givesabandac."{a,b}x{c,d}"givesaxc,axd,bxcandbxd."abc"gives justabc."README.md,resources/js/{app,boot,comp/{a,b}}.js"givesREADME.md,resources/js/app.js,resources/js/boot.js,resources/js/comp/a.jsandresources/js/comp/b.js.