Problem overview
A compressed folder listing is a Token List: text in which commas separate alternatives and braces group alternatives that are glued to the text around them. In my_{first,second}_folder/{a,b}{.js,.py}, the braces after my_ offer first or second, and the two groups at the end offer a or b followed by .js or .py. The method decompress receives such a string and returns the full list of paths, in any order.
For the example above the result has 2 × 2 × 2 = 8 paths, from my_first_folder/a.js to my_second_folder/b.py. For README.md,resources/js/{app,boot,comp/{a,b}}.js the result is README.md, resources/js/app.js, resources/js/boot.js, resources/js/comp/a.js and resources/js/comp/b.js.
Approach: one recursive call per pair of braces
The input is nested: a group can contain commas and more groups. Nesting is the natural cue for recursion. Let parsePaths read characters starting at the current position and produce every path of the current level, stopping at the } that closes it (or at the end of the input at the top level).
While reading a level, keep two lists:
currentLevelholds paths that are complete, which means they were ended by a comma.stringsholds the paths being built since the last comma. It starts as[""], one empty path, so there is something to append the first characters to.
Each character is handled by its kind:
- A plain character is appended to every string in
strings, because all the paths in progress share it. - A comma ends the current alternative: move
stringsintocurrentLeveland start over with[""]. - An opening brace starts a nested level. The recursive call returns that level's alternatives, and every string built so far is combined with every one of them. That product is why the example with two groups gives 8 paths.
- A closing brace ends the level, and the function returns to its caller.
The recursion needs a position that all the calls share. When a nested call finishes, the caller must continue after the closing brace, not from where it started. A local variable would restart in each call, so the position is stored on the object: the property index.
Step by step
- Delegate in
decompress. It returnsparsePaths(Array(input)). The string becomes an array of characters because a SwiftStringcan't be indexed with an integer. - Declare
parsePathswith an unlabeled[Character]parameter and a[String]result. - Create
currentLevelas an empty array. - Create
stringsas[""]. - Add the shared position. The class already has
var index: Int. Aninit()sets it to 0, because Swift requires every stored property to have a value after initialization. - Loop while
index < input.count. - Handle
{. Moveindexpast the brace, callparsePaths(input)and store the result innextLevel. When that call returns,indexpoints at the}that closed the nested level. - Combine. Replace
stringswithconcatAllPairs(strings, nextLevel): every existing prefix paired with every nested alternative. - Handle
}. Break out of the loop and let the function return. - Handle
,. Append all ofstringstocurrentLevelwithappend(contentsOf:)and resetstringsto[""]. - Handle anything else. Add the character to the end of every string in
strings. - Advance. At the bottom of the loop,
index += 1. After a nested call this steps over the}that ended it. - Flush. After the loop, the last alternative never met a comma, so append
stringstocurrentLevelonce more and returncurrentLevel. - Write
concatAllPairs: two nested loops overfirstandsecond, appendingfirstPart + secondPartto a result array.
The solution in Swift
class Solution {
func concatAllPairs(_ first: [String], _ second: [String]) -> [String] {
var result = [String]()
for firstPart in first {
for secondPart in second {
result.append(firstPart + secondPart)
}
}
return result
}
var index: Int
init() {
index = 0
}
func parsePaths(_ input: [Character]) -> [String] {
var currentLevel = [String]()
var strings = [""]
while index < input.count {
if input[index] == "{" {
index += 1
let nextLevel = parsePaths(input)
strings = concatAllPairs(strings, nextLevel)
} else if input[index] == "}" {
break
} else if input[index] == "," {
currentLevel.append(contentsOf: strings)
strings = [""]
} else {
for i in 0..<strings.count {
strings[i] += String(input[index])
}
}
index += 1
}
currentLevel.append(contentsOf: strings)
return currentLevel
}
func decompress(_ input: String) -> [String] {
return parsePaths(Array(input))
}
}
The Swift details worth knowing:
- Characters and strings. Swift writes a character literal with double quotes, like a string. In
input[index] == "{"the literal is inferred to be aCharacterbecauseinputis a[Character]. Adding a character to a string needs a conversion, henceString(input[index]). - Classes need initializers. A stored property without a default value, like
index, must be set ininit(). Writingvar index = 0would also work, but the lesson uses the explicit form. - State on the object. Since
indexbelongs to theSolutioninstance and not to one call, every recursive call advances the same counter. The price is that an instance can parse only one string: afterdecompress("a,b"),indexstays at the end, and a second call on the same object returns[""]. A freshSolution()for each input avoids that. append(contentsOf:)adds all elements of another array to the end of this one.- Value types.
strings[i] += ...changes the string stored in the local array. Because arrays and strings are values, the paths already moved intocurrentLevelare separate copies and are not affected. - Recursion inside a method. A method can call itself by name, and it reads and writes the instance's
indexwithout extra syntax.
Complexity
Let M be the number of resulting paths and P their average length.
Time: proportional to the characters produced. Each call of concatAllPairs builds one new string per pair, so its cost is the combined length of those strings. The total is at least O(M · P) for the final output, plus the intermediate products formed at inner levels. The growth is exponential in the input by nature: k groups of two choices give 2^k paths, and any solution has to produce them all.
Space: O(M · P). All the paths are stored in the result. The recursion depth is the deepest nesting of braces.
Edge cases and common mistakes
- No braces.
ab,acreturns["ab", "ac"]: the comma branch storesab, and the final flush storesac. - Adjacent groups.
{a,b}x{c,d}returnsaxc,axd,bxc,bxd. Each group multiplies the paths built so far. - Empty input. The loop never runs, and the result is
[""], one empty path. - An empty alternative. In
a{b,}the second alternative is empty, so the result is["ab", "a"]. - Forgetting the final flush. Without the append after the loop, the last alternative at every level would be lost.
- Using a local position. A local variable restarts at 0 in the recursive call, which re-reads the same characters forever and ends in a stack overflow.
- Not skipping the closing brace. Without the
index += 1at the bottom, the caller would see the same}and stop its own level too early.
Testing
ab,acgivesabandac.{a,b}x{c,d}givesaxc,axd,bxc,bxd.README.md,resources/js/{app,boot,comp/{a,b}}.jsgives the five paths listed above.my_{first,second}_folder/{a,b}{.js,.py}gives 8 paths.a{b,}givesabanda.
