Start learning free

LESSON 347 OF 348 · RECURSION

Decompress File Paths in Kotlin: Recursive Descent Parsing

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

KOTLIN · RECURSION

Decompress File Paths in Kotlin, explained

Problem overview

A list of paths can be written compactly by grouping common parts in braces. The string "my_{first,second}_folder/{a,b}{.js,.py}" stands for every combination of the choices inside the braces. The function decompress receives such a string, called a Token List, and returns the full list of paths it stands for. The order of the result doesn't matter.

A Token List is a sequence of pieces: plain text, or a brace group {...} whose items are separated by commas and are Token Lists themselves. A comma outside any braces separates whole paths. For example:

"ab,ac" gives ["ab", "ac"], two separate paths.
"a{b,c}" gives ["ab", "ac"].
"{a,b}x{c,d}" gives ["axc", "axd", "bxc", "bxd"]: every choice from the first group with every choice from the second.

Approach: recursion that mirrors the nesting

Braces nest, so the natural tool is recursion. Define one function, parsePaths, that reads one level of the string and returns the list of paths that level expands to. Whenever it meets {, it calls itself to expand the nested level, and when it meets the matching } it stops and hands control back. This style is called recursive descent.

Inside one level, the function keeps two lists:

strings, the partial paths built since the last comma, starting as [""]. Each plain letter is appended to every string in it.
currentLevel, the finished paths of this level. At a comma, strings is moved into it and restarted.

When a nested group returns a list nextLevel, every partial path must be combined with every item of the group. That product of two lists is what concatAllPairs computes. After {a,b}, for instance, strings goes from [""] to ["a", "b"], and a following group {c,d} turns it into ["ac", "ad", "bc", "bd"].

The recursive calls must keep reading where the previous call stopped, so the position can't be a local variable. It lives on the object as the property index, which all the calls share.

Step by step

Delegate. decompress simply returns parsePaths(input). The helper does the work.
Declare parsePaths with a String parameter and a MutableList<String> result.
Create currentLevel as a val holding an ArrayList<String>. A val fixes the reference, not the contents, so the list can still grow.
Create strings as a var of type MutableList<String>, started with arrayListOf(""). It needs the single empty string so the first letters have something to attach to, and it needs var and the explicit type because it is later replaced by the list that concatAllPairs returns.
Set up the shared position. The class declares var index: Int, and a secondary constructor() sets it to 0. Kotlin requires a property to be initialised, and the property has no initial value here.
Loop while index < input.length.
On '{', increment index so the recursive call starts after the brace, call parsePaths(input) into nextLevel, and replace strings with concatAllPairs(strings, nextLevel).
On '}', break. This level is finished, and index points at the closing brace.
On ',', add all of strings to currentLevel and reset strings to arrayListOf("").
Otherwise it's a letter: loop over 0 until strings.size and append the character to each string, writing the new string back into the list.
Advance. After the branches, index++ moves to the next character. After a nested call, this also steps past the } that ended it.
Flush and return. After the loop, add what is left in strings to currentLevel and return it. The last path of a level never meets a comma.
Write concatAllPairs(first, second), which creates an empty ArrayList and, for each firstPart in first and each secondPart in second, adds firstPart + secondPart. It returns the list.

The solution in Kotlin

class Solution {
    fun concatAllPairs(first: List<String>, second: List<String>): MutableList<String> {
        val result = ArrayList<String>()
        for (firstPart in first) {
            for (secondPart in second) {
                result.add(firstPart + secondPart)
            }
        }
        return result
    }

    var index: Int
    constructor() {
        index = 0
    }

    fun parsePaths(input: String): MutableList<String> {
        val currentLevel = ArrayList<String>()
        var strings: MutableList<String> = arrayListOf("")
        while (index < input.length) {
            if (input[index] == '{') {
                ++index
                val nextLevel = parsePaths(input)
                strings = concatAllPairs(strings, nextLevel)
            } else if (input[index] == '}') {
                break
            } else if (input[index] == ',') {
                currentLevel.addAll(strings)
                strings = arrayListOf("")
            } else {
                for (i in 0 until strings.size) {
                    strings[i] = strings[i] + input[index]
                }
            }
            index++
        }
        currentLevel.addAll(strings)
        return currentLevel
    }

    fun decompress(input: String): MutableList<String> {
        return parsePaths(input)
    }
}

The Kotlin details worth a closer look:

A property needs a value. A Kotlin class property must be initialised when it is declared or in the constructor. var index: Int has no initialiser, so the secondary constructor() assigns index = 0. Writing var index = 0 would do the same in one line.
Read-only List parameters, mutable results. concatAllPairs only reads its inputs, so they are declared List<String>, and the MutableList passed in is accepted. It returns a MutableList so that strings can hold it and be edited.
Why strings has an explicit type. arrayListOf("") alone would give the variable the type ArrayList<String>. Declaring MutableList<String> lets the same variable also hold the result of concatAllPairs.
Strings are immutable. strings[i] = strings[i] + input[index] builds a new String (a String plus a Char) and stores it in position i. The old string is not changed.
0 until strings.size excludes its upper bound, so it covers exactly the valid indices.
++index and index++ both add 1 here, because the result of the expression isn't used.
Comparing characters. input[index] == '{' compares a Char to a character literal in single quotes. Double quotes would make a String, which can't be compared with a Char.

Complexity

Let n be the length of the input and R the total number of characters in the answer.

Time: proportional to the size of the output, roughly O(R). Every input character is read once, but a letter is appended to every partial path and each brace group multiplies the number of paths. The output itself can grow exponentially with the input ({a,b}{c,d}{e,f} and so on doubles with every group), so no algorithm can beat the output size.

Space: the result takes O(R). The recursion is as deep as the nesting of braces, at most O(n) frames.

Edge cases and common mistakes

A path with no braces. "abc" gives ["abc"]. The final flush after the loop is what adds it, since no comma ever moves it into currentLevel.
Nested groups. "a{b{c,d},e}" gives ["abc", "abd", "ae"]. The inner group is expanded by a deeper call and combined with the b before it.
A group at the start. "{a,b}" gives ["a", "b"], because strings starts as [""] and the product with the group keeps every item.
Missing the flush after the loop. The last path of every level would be lost.
Forgetting index++ after a nested call. The closing } would be seen again by the caller and end the caller's level too early.
Using a local position variable. Every recursive call would start at 0 and the string would be re-read forever.
Reusing one Solution object. index stays at the end of the string after a call. A second decompress on the same object starts there, finds nothing to read and returns a list with one empty string. Create a new Solution() for each input, or set index = 0 at the start of decompress.
Appending to strings in place. Strings can't change, so writing strings[i] + input[index] without assigning it back leaves the list unchanged.

Testing

"ab,ac" gives ["ab", "ac"].
"{a,b}x{c,d}" gives ["axc", "axd", "bxc", "bxd"].
"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"] in that order.
"my_{first,second}_folder/{a,b}{.js,.py}" gives the eight paths from my_first_folder/a.js to my_second_folder/b.py.
"a{b{c,d},e}" gives ["abc", "abd", "ae"].

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

Start learning free