LeetCode: Brace Expansion

Posted on August 9, 2019July 26, 2020 by braindenny

Brace Expansion

Similar Problems:

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 <= S.length <= 50
There are no nested curly brackets.
All characters inside a pair of consecutive opening and ending curly brackets are different.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/brace-expansion
// Basic Ideas: backtracking
//
// Complexity:
import ("sort"
        "strings")
func backtrack(combination string, l [][]string, pos int, res *[]string) {
    if pos == len(l) {
        *res = append(*res, combination)
        return
    }
    for _, ch := range l[pos] {
        backtrack(combination+string(ch), l, pos+1, res)
    }
}
func expand(S string) []string {
    l := [][]string{}
    entry := ""
    for _, ch := range S+"{" {
        if ch == '{' || ch == '}' {
            if len(entry) != 0 {
                items := strings.Split(entry, ",")
                sort.Slice(items, func(i, j int) bool {
                    return items[i] < items[j]
                })
                l = append(l, items)
            }
            entry = ""
        } else {
            entry = entry+string(ch)
        }
    }

    res := []string{}
    backtrack("", l, 0, &res)
    return res
}

Post Views: 0