package LeetCode_1087

/**
 * 1087.Brace-Expansion (prime)
 * https://leetcode.com/problems/brace-expansion/
 *
 * A string S represents a list of words. Each letter in the word has 1 or more options.
 * If there is one option, the letter is represented as is.
 * If there is more than one option, then curly braces delimit the options.
 * For example, "{a,b,c}" represents options ["a", "b", "c"].
For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].
Return all words that can be formed in this manner, in lexicographical order.

Example 1:
Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:
Input: "abcd"
Output: ["abcd"]

Note:
1. 1 <= S.length <= 50
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.
 * */
class Solution {
    /*
    * solution: DFS, Time:O(2^n), Space:O(n)
    * 1. create list format, for example:{a,b}c{d,e}f => [[a,b], [c], [d, e]]
    * 2. dfs to create result
    * */
    fun expand(s: String): Array<String?> {
        val result = ArrayList<String>()
        val lists = ArrayList<ArrayList<String>>()
        var i = 0
        var j = 0
        while (i < s.length) {
            val c = s[i]
            if (c != '{') {
                //is letter, append it
                lists.add(ArrayList(listOf(c.toString())))
            } else {
                //keep track to find out all letter
                j = i
                while (j < s.length && s[j] != '}') {
                    j++
                }
                val rString = s.substring(i + 1, j)
                val rList = rString.split(",")
                rList.sorted()
                lists.add(ArrayList(rList))
                //move the i to right
                i = j
            }
            i++
        }
        dfs(0, StringBuilder(), lists, result)
        //set for result
        val arrays = arrayOfNulls<String>(result.size)
        for (i in result.indices) {
            arrays[i] = result[i]
        }
        return arrays
    }

    private fun dfs(index: Int, sb: StringBuilder, lists: ArrayList<ArrayList<String>>, res: ArrayList<String>) {
        //if enumerated all element in lists, add into res
        if (index == lists.size) {
            res.add(sb.toString())
            return
        }
        for (str in lists[index]) {
            sb.append(str)
            dfs(index + 1, sb, lists, res)
            //for next level
            sb.setLength(sb.length - 1)
        }
    }
}