Start learning free

LESSON 371 OF 414 · RECURSION

Decompress File Paths in Scala: Recursive Token List Parser

Practice Read the full explanation

A comma separated list of strings can be compressed by finding common substrings and grouping those strings together into Token Lists

More formally, a Token List is a list where each item can be one of the following:

a string
a concatenation of Token Lists

Examples:

ab,ac => a{b,c}
ac,ad,bc,bd => {a,b}{c,d}
axc,axd,bxc,bxd => {a,b}x{c,d}

This technique is used to compress folder paths since a folder like

README.md
resources/
    js/
        app.js
        boot.js
        comp/
            a.js
            b.js

can be represented as a list of strings:

[
    "README.md",
    "resources/js/app.js",
    "resources/js/boot.js",
    "resources/js/comp/a.js",
    "resources/js/comp/b.js"
]

and further encoded into comma separated string

“README.md,resources/js/app.js,resources/js/boot.js,resources/js/comp/a.js,resources/js/comp/b.js”

and then we can compress them to the following Token List:

README.md,resources/js/{app,boot,comp/{a,b}}.js

Given a Token List representing a compressed folder, return the initial list of paths.

Example 1:

Input:
"resources/{js/{app.js,comp/{a.js,b.js},boot.js}},README.md"

Output: [
    "README.md",
    "resources/js/app.js",
    "resources/js/boot.js",
    "resources/js/comp/a.js",
    "resources/js/comp/b.js"
]

Example 2:

Input:
"my_{first,second}_folder/{a,b}{.js,.py}"

Output: [
    "my_first_folder/a.js",
    "my_first_folder/a.py",
    "my_first_folder/b.js",
    "my_first_folder/b.py",
    "my_second_folder/a.js",
    "my_second_folder/a.py",
    "my_second_folder/b.js",
    "my_second_folder/b.py"
]

Note: The resulting array can be in any order

STEP 1 OF 19

Guided

Ctrl + Enter to check

SCALA · RECURSION

Decompress File Paths in Scala, explained

Problem overview

The method decompress receives a string called input that holds a Token List: pieces of text separated by commas, where braces group alternatives. It returns an ArrayBuffer[String] with every path the token list stands for, in any order.

The rules are small. A comma separates alternatives. Text next to a group is joined with every alternative inside it, and two groups next to each other produce every combination. So a{b,c} means ab and ac, and {a,b}{c,d} means ac, ad, bc and bd. Groups can be nested, as in README.md,resources/js/{app,boot,comp/{a,b}}.js, which expands to 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

Nested braces have the same shape as the whole input: a list of alternatives separated by commas. That is a hint for recursion. A function parsePaths reads characters and produces all the paths for one level, stopping at the } that closes it or at the end of the input. When it meets a {, it calls itself to parse the inside, and uses the result as one more building block.

Two collections do the bookkeeping at each level:

currentLevel holds the finished paths of this level, the ones completed by a comma.
strings holds the paths being built since the last comma. It starts with a single empty string. A plain character is appended to every string in it. A group multiplies it: every string in progress is combined with every string the group produced.

The recursive calls must continue where the previous call stopped, so the position in the input is shared by all calls. The solution keeps it in a field of the class, index. After a nested call returns, index points at the } that ended it, and the loop's final index += 1 steps past that brace.

Step by step

Delegate. decompress only calls parsePaths(input). The call is its last expression, so Scala returns it.
Declare parsePaths above it. It takes the input and returns an ArrayBuffer[String].
Create currentLevel as a val holding an empty ArrayBuffer[String]. A val fixes the reference, and the buffer can still grow.
Create strings as a var holding a buffer with one empty string. It is a var because it is replaced later. The empty string gives the first characters something to be appended to.
Add the shared position. var index: Int = 0 goes in the class body, above parsePaths. A local variable would start again at 0 in every recursive call.
Loop with while (index < input.length) inside a breakable block, because the loop must be able to end early at a closing brace.
Open brace. If input(index) == '{', move index past it with index += 1.
Recurse. The call parsePaths(input) returns nextLevel, all paths of the group.
Combine. concatAllPairs(strings, nextLevel) pairs every string in progress with every string of the group, and the result replaces strings.
Close brace. If the character is '}', the group that this call was asked to parse is finished, so break() leaves the loop.
Comma. The paths in strings are complete. Append them to currentLevel with ++= and reset strings to a buffer with one empty string.
Any other character. Append it to every string in strings. Strings are immutable, so the loop over strings.indices writes the new string back into the buffer.
Advance with index += 1 after all the branches. After a nested call, this also steps past the } that ended it.
Flush. When the loop ends, strings may hold paths that no comma ever completed. Append them to currentLevel and return it.
Write concatAllPairs. It takes two Iterable[String] values, loops over first and, inside it, over second, and appends firstPart + secondPart to a new result buffer, which it returns.

The solution in Scala

class Solution {
    def concatAllPairs(first: Iterable[String], second: Iterable[String]): ArrayBuffer[String] = {
        val result = ArrayBuffer[String]()
        for (firstPart <- first) {
            for (secondPart <- second) {
                result += (firstPart + secondPart)
            }
        }
        result
    }

    var index: Int = 0

    def parsePaths(input: String): ArrayBuffer[String] = {
        val currentLevel = ArrayBuffer[String]()
        var strings = ArrayBuffer[String]("")
        breakable {
            while (index < input.length) {
                if (input(index) == '{') {
                    index += 1
                    val nextLevel = parsePaths(input)
                    strings = concatAllPairs(strings, nextLevel)
                } else if (input(index) == '}') {
                    break()
                } else if (input(index) == ',') {
                    currentLevel ++= strings
                    strings = ArrayBuffer[String]("")
                } else {
                    for (i <- strings.indices) {
                        strings(i) = strings(i) + input(index)
                    }
                }
                index += 1
            }
        }
        currentLevel ++= strings
        currentLevel
    }

    def decompress(input: String): ArrayBuffer[String] = {
        parsePaths(input)
    }
}

The code uses ArrayBuffer and breakable, so the file needs import scala.collection.mutable.ArrayBuffer and import scala.util.control.Breaks._. The Scala details worth a closer look:

break() works only inside breakable. Scala has no break keyword. The call throws a control exception, and the nearest enclosing breakable catches it. Each recursive call has its own breakable, so a } ends only the call that is reading that group.
Characters. input(index) is a Char, written with single quotes: '{'. Appending it to a String with + adds its text.
+= and ++=. On an ArrayBuffer, += appends one element and ++= appends all the elements of another collection.
Iterable[String]. ArrayBuffer[String] is an Iterable[String], so strings and nextLevel can be passed straight to concatAllPairs.
State on the object. Because index lives in the Solution object, a second call to decompress on the same object starts with index already at the end of the previous input. On one Solution instance, decompress("a{b,c}") gives ab and ac, and calling it again returns a buffer with only the empty string. Create a new Solution for each input, or reset index to 0 first.

Complexity

Time and space: proportional to the size of the output. Let T be the total number of characters in all returned paths. Every input character is appended to each string in progress at its level, and concatAllPairs builds each combined string once per level of nesting that it passes through. The work is therefore about T times a factor up to the nesting depth. The output can be much longer than the input: a token list such as {a,b}{c,d}{e,f} has 15 characters and expands to 8 paths.

The recursion depth equals the nesting depth of the braces, which is small for real paths.

Edge cases and common mistakes

No braces or commas. "abc" gives ["abc"]. Without the final flush, nothing would be returned.
Empty input. "" gives a buffer holding one empty string, because strings starts with "".
Empty alternative. a{b,} gives ab and a, and a{} gives a.
Duplicates are kept. {a,a} gives a twice. The method doesn't remove duplicates.
Side by side groups. my_{first,second}_folder/{a,b}{.js,.py} gives eight paths, the product 2 * 2 * 2.
Order. Results come out in the order the alternatives appear. For resources/{js/{app.js,comp/{a.js,b.js},boot.js}},README.md, README.md comes last. Any order is accepted.
Using a local index. A variable declared inside parsePaths restarts at 0 in every call, so the nested call would read the input again from the beginning.
Forgetting to reset strings after a comma. The paths already moved to currentLevel would be extended with the next alternative's characters.

Testing

ab,ac gives ab and ac.
{a,b}x{c,d} gives axc, axd, bxc and bxd.
README.md,resources/js/{app,boot,comp/{a,b}}.js gives README.md, resources/js/app.js, resources/js/boot.js, resources/js/comp/a.js and resources/js/comp/b.js.
a{b,} gives ab and a.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free