1096. Brace Expansion II

Description

Under the grammar given below, strings can represent a set of lowercase words. Let R(expr) denote the set of words the expression represents.

The grammar can best be understood through simple examples:

Single letters represent a singleton set containing that word.
- R("a") = {"a"}
- R("w") = {"w"}
When we take a comma-delimited list of two or more expressions, we take the union of possibilities.
- R("{a,b,c}") = {"a","b","c"}
- R("{ {a,b},{b,c} }") = {"a","b","c"} (notice the final set only contains each word at most once)
When we concatenate two expressions, we take the set of possible concatenations between two words where the first word comes from the first expression and the second word comes from the second expression.
- R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
- R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}

Formally, the three rules for our grammar:

For every lowercase letter x, we have R(x) = {x}.
For expressions e₁, e₂, ... , e_k with k >= 2, we have R({e₁, e₂, ...}) = R(e₁) ∪ R(e₂) ∪ ...
For expressions e₁ and e₂, we have R(e₁ + e₂) = {a + b for (a, b) in R(e₁) × R(e₂)}, where + denotes concatenation, and × denotes the cartesian product.

Given an expression representing a set of words under the given grammar, return the sorted list of words that the expression represents.

Example 1:

Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]

Example 2:

Input: expression = "{ {a,z},a{b,c},{ab,z} }"
Output: ["a","ab","ac","z"]
Explanation: Each distinct word is written only once in the final answer.

Constraints:

1 <= expression.length <= 60
expression[i] consists of '{', '}', ','or lowercase English letters.
The given expression represents a set of words based on the grammar given in the description.

Solutions

Solution 2: Grammar Parsing

Thinking

Solution 1 copies the still-unexpanded suffix into every alternative. A nested three-way union such as ${\ldots{a,b,c},a,b}$ therefore repeats the same suffix and takes $O(3^{n/6})$ time, even when only a constant number of words are distinct.

Commas occur only inside braces and mean union. Adjacent factors outside commas mean concatenation. A left-to-right parse evaluates each subexpression once.

A factor is a run of lowercase letters or a brace expression. Concatenation is the Cartesian product of the current set with the factor, and commas take the union of those products. A hash set removes duplicates, and the final set is sorted.

Let $s$ be the expression. Starting at index $i$, define two functions.

$\textit{expr}(i)$ parses a union of terms. It parses one $\textit{term}$, and while the next character is a comma it skips the comma, parses another $\textit{term}$, and unions the sets together. It stops at } or the end of $s$.

$\textit{term}(i)$ parses a concatenation of factors, starting from ${\varepsilon}$. A { recursively parses the inner $\textit{expr}$ and then skips the matching }. Otherwise the factor is the following run of lowercase letters. The current set is replaced by its Cartesian product with that factor. The function returns at a comma, a }, or the end of $s$.

Sort the set returned by $\textit{expr}(0)$. Each subexpression is parsed once, so the suffix is no longer copied and rescanned on every branch.

The time complexity is $O(n^2 \times 3^{n/7})$ and the space complexity is $O(n \times 3^{n/7})$, where $n$ is the length of the expression. The worst case is a concatenation of {a,b,c} groups, which produces $\Theta(3^{n/7})$ words of length $O(n)$. Building them costs $O(n \times 3^{n/7})$ and sorting them costs $O(n^2 \times 3^{n/7})$. A nested three-way union keeps every intermediate set at size $O(1)$, so that input takes only $O(n)$ time.

class Solution {
    private TreeSet<String> s = new TreeSet<>();

    public List<String> braceExpansionII(String expression) {
        dfs(expression);
        return new ArrayList<>(s);
    }

    private void dfs(String exp) {
        int j = exp.indexOf('}');
        if (j == -1) {
            s.add(exp);
            return;
        }
        int i = exp.lastIndexOf('{', j);
        String a = exp.substring(0, i);
        String c = exp.substring(j + 1);
        for (String b : exp.substring(i + 1, j).split(",")) {
            dfs(a + b + c);
        }
    }
}


// Solution 2
class Solution {
    private String exp;
    private int i;

    public List<String> braceExpansionII(String expression) {
        exp = expression;
        i = 0;
        List<String> ans = new ArrayList<>(expr());
        Collections.sort(ans);
        return ans;
    }

    private Set<String> expr() {
        Set<String> res = term();
        while (i < exp.length() && exp.charAt(i) == ',') {
            ++i;
            res.addAll(term());
        }
        return res;
    }

    private Set<String> term() {
        Set<String> res = new HashSet<>();
        res.add("");
        while (i < exp.length() && exp.charAt(i) != ',' && exp.charAt(i) != '}') {
            Set<String> cur = new HashSet<>();
            if (exp.charAt(i) == '{') {
                ++i;
                cur = expr();
                ++i;
            } else {
                int j = i + 1;
                while (j < exp.length() && exp.charAt(j) >= 'a' && exp.charAt(j) <= 'z') {
                    ++j;
                }
                cur.add(exp.substring(i, j));
                i = j;
            }
            Set<String> nxt = new HashSet<>();
            for (String a : res) {
                for (String b : cur) {
                    nxt.add(a + b);
                }
            }
            res = nxt;
        }
        return res;
    }
}

class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        dfs(expression);
        return vector<string>(s.begin(), s.end());
    }

private:
    set<string> s;

    void dfs(string exp) {
        int j = exp.find_first_of('}');
        if (j == string::npos) {
            s.insert(exp);
            return;
        }
        int i = exp.rfind('{', j);
        string a = exp.substr(0, i);
        string c = exp.substr(j + 1);
        stringstream ss(exp.substr(i + 1, j - i - 1));
        string b;
        while (getline(ss, b, ',')) {
            dfs(a + b + c);
        }
    }
};


// Solution 2
class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        exp = std::move(expression);
        i = 0;
        set<string> ans = parseExpr();
        return vector<string>(ans.begin(), ans.end());
    }

private:
    string exp;
    int i = 0;

    set<string> parseExpr() {
        set<string> res = parseTerm();
        while (i < exp.size() && exp[i] == ',') {
            ++i;
            set<string> other = parseTerm();
            res.insert(other.begin(), other.end());
        }
        return res;
    }

    set<string> parseTerm() {
        set<string> res{""};
        while (i < (int) exp.size() && exp[i] != ',' && exp[i] != '}') {
            set<string> cur;
            if (exp[i] == '{') {
                ++i;
                cur = parseExpr();
                ++i;
            } else {
                int j = i + 1;
                while (j < (int) exp.size() && exp[j] >= 'a' && exp[j] <= 'z') {
                    ++j;
                }
                cur.insert(exp.substr(i, j - i));
                i = j;
            }
            set<string> nxt;
            for (const string& a : res) {
                for (const string& b : cur) {
                    nxt.insert(a + b);
                }
            }
            res.swap(nxt);
        }
        return res;
    }
};

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def dfs(exp):
            j = exp.find('}')
            if j == -1:
                s.add(exp)
                return
            i = exp.rfind('{', 0, j - 1)
            a, c = exp[:i], exp[j + 1 :]
            for b in exp[i + 1 : j].split(','):
                dfs(a + b + c)

        s = set()
        dfs(expression)
        return sorted(s)



# Solution 2
class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def expr(i: int):
            res, i = term(i)
            while i < len(expression) and expression[i] == ',':
                other, i = term(i + 1)
                res |= other
            return res, i

        def term(i: int):
            res = {''}
            while i < len(expression) and expression[i] not in ',}':
                if expression[i] == '{':
                    cur, i = expr(i + 1)
                    i += 1
                else:
                    j = i + 1
                    while j < len(expression) and expression[j].islower():
                        j += 1
                    cur = {expression[i:j]}
                    i = j
                res = {a + b for a in res for b in cur}
            return res, i

        ans, _ = expr(0)
        return sorted(ans)

func braceExpansionII(expression string) []string {
	s := map[string]struct{}{}
	var dfs func(string)
	dfs = func(exp string) {
		j := strings.Index(exp, "}")
		if j == -1 {
			s[exp] = struct{}{}
			return
		}
		i := strings.LastIndex(exp[:j], "{")
		a, c := exp[:i], exp[j+1:]
		for _, b := range strings.Split(exp[i+1:j], ",") {
			dfs(a + b + c)
		}
	}
	dfs(expression)
	ans := make([]string, 0, len(s))
	for k := range s {
		ans = append(ans, k)
	}
	sort.Strings(ans)
	return ans
}


// Solution 2
func braceExpansionII(expression string) []string {
	exp := expression
	i := 0
	var parseExpr func() map[string]struct{}
	var parseTerm func() map[string]struct{}
	parseExpr = func() map[string]struct{} {
		res := parseTerm()
		for i < len(exp) && exp[i] == ',' {
			i++
			for w := range parseTerm() {
				res[w] = struct{}{}
			}
		}
		return res
	}
	parseTerm = func() map[string]struct{} {
		res := map[string]struct{}{"": {}}
		for i < len(exp) && exp[i] != ',' && exp[i] != '}' {
			cur := map[string]struct{}{}
			if exp[i] == '{' {
				i++
				cur = parseExpr()
				i++
			} else {
				j := i + 1
				for j < len(exp) && exp[j] >= 'a' && exp[j] <= 'z' {
					j++
				}
				cur[exp[i:j]] = struct{}{}
				i = j
			}
			nxt := map[string]struct{}{}
			for a := range res {
				for b := range cur {
					nxt[a+b] = struct{}{}
				}
			}
			res = nxt
		}
		return res
	}
	all := parseExpr()
	ans := make([]string, 0, len(all))
	for w := range all {
		ans = append(ans, w)
	}
	sort.Strings(ans)
	return ans
}

function braceExpansionII(expression: string): string[] {
    const dfs = (exp: string) => {
        const j = exp.indexOf('}');
        if (j === -1) {
            s.add(exp);
            return;
        }
        const i = exp.lastIndexOf('{', j);
        const a = exp.substring(0, i);
        const c = exp.substring(j + 1);
        for (const b of exp.substring(i + 1, j).split(',')) {
            dfs(a + b + c);
        }
    };
    const s: Set<string> = new Set();
    dfs(expression);
    return Array.from(s).sort();
}



// Solution 2
function braceExpansionII(expression: string): string[] {
    let i = 0;
    const expr = (): Set<string> => {
        const res = term();
        while (i < expression.length && expression[i] === ',') {
            ++i;
            for (const w of term()) {
                res.add(w);
            }
        }
        return res;
    };
    const term = (): Set<string> => {
        let res = new Set<string>(['']);
        while (i < expression.length && expression[i] !== ',' && expression[i] !== '}') {
            let cur: Set<string>;
            if (expression[i] === '{') {
                ++i;
                cur = expr();
                ++i;
            } else {
                let j = i + 1;
                while (j < expression.length && expression[j] >= 'a' && expression[j] <= 'z') {
                    ++j;
                }
                cur = new Set([expression.slice(i, j)]);
                i = j;
            }
            const nxt = new Set<string>();
            for (const a of res) {
                for (const b of cur) {
                    nxt.add(a + b);
                }
            }
            res = nxt;
        }
        return res;
    };
    return Array.from(expr()).sort();
}

1096 - Brace Expansion II

1096. Brace Expansion II

Description

Solutions

Solution 2: Grammar Parsing

All Problems

All Solutions

Welcome to Subscribe On Youtube

1096. Brace Expansion II

Description

Solutions

Solution 2: Grammar Parsing

All Problems

All Solutions