1096. Brace Expansion II

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

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 2 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 3 rules for our grammar:

• For every lowercase letter x, we have R(x) = {x}

• For expressions e_1, e_2, ... , e_k

  with k >= 2, we have R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...

• For expressions e_1and e_2, we have R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}, where + denotes concatenation, and × denotes the cartesian product.

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

Example 1:

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

Example 2:

Input: "{{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. 1 <= expression.length <= 50

2. expression[i]consists of'{','}',','or lowercase English letters.

3. The given expressionrepresents a set of words based on the grammar given in the description.

Thoughts:

1. Recursion conditioned on level of braces (Original Post):

   1. for level larger than 1, recursively reduce level of braces down by 1.

   2. for level == 0, if there is "," , then initialize a new group by appending a [] to the groups.

   3. Finally, for each group, calculate the cartesian product and then join it with other groups, and then filter redundant elements and sort the filtered elements.

2. Recursion based on finite (3) state graph (Original Post):

   1. state 0: deal with a single string

   2. state 1: deal with a set with the form {x}. x can be valid expression

   3. state 2: deal with union of sets: {a, b, c, d}.

   4. state 3: deal with cartesian product of sets: {abcd}

   5. Relationship:

      1. state 1 is { state 2 }

      2. state 2 is from *state 3, separated by ","

      3. state 3 is from combination of state 0 and state 1

3. Recursion with simplified 2 state graph: 1. union: a,b

   1. cartesian product: abcd

Code:

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        groups = [[]]
        level = 0 

        for i, c in enumerate(expression):
            if c == '{':
                if level == 0:
                    start = i + 1
                level += 1
            elif c == '}':
                level -= 1
                if level == 0:
                    groups[-1].append(self.braceExpansionII(expression[start:i]))
            elif level == 0:
                if c == ',':
                    groups += [[]]
                else:
                    groups[-1].append(c)

        words = set()
        for group in groups:
            words |= set(map(''.join, itertools.product(*group)))
        return sorted(words)

Code: Finite state graph

class Solution {
    set<string> merge(set<string>&a, set<string>&b){
        if(a.size() == 0){
            return b;
        }
        if(b.size() == 0){
            return a;
        }
        set<string> ans;
        for(auto& v1: a){
            for(auto& v2: b){
                ans.insert(v1+v2);
            }
        }
        return ans;
    }

    //{a,b,c}
    set<string> parseRule1(const string& str, int& i){
        set<string> ans;
        i++;
        ans = parseRule2(str, i);
        i++;
        return ans;
    }
    //{a,b},{c,d}
    set<string> parseRule2(const string& str, int& i){
        set<string> ans;
        ans = parseRule3(str, i);
        while(i<str.length()){
            if(str[i] != ','){
                break;
            }
            i++;
            set<string> tmp = parseRule3(str, i);
            ans.insert(tmp.begin(), tmp.end());
        }
        return ans;
    }
    //a{c,d}b{e,f}
    set<string> parseRule3(const string& str, int& i){
        set<string> ans;
        while(i < str.length()){
            if(str[i] == '}' || str[i] == ','){
                break;
            }
            if(str[i] == '{'){
                set<string> tmp = parseRule1(str, i);
                ans = merge(ans, tmp);
            }else{
                set<string> tmp;
                string tmpStr;
                while(i < str.length() && str[i] <= 'z' && str[i] >= 'a'){
                    tmpStr.push_back(str[i++]);
                }
                tmp.insert(tmpStr); /* tmp is alwasy a singleton set*/
                ans = merge(ans, tmp);
            }
        }
        return ans;
    }
public:
    vector<string> braceExpansionII(string str) {
        int pos = 0;
        set<string> ans = parseRule2(str, pos);
        return vector<string>(ans.begin(), ans.end());
    }
};

Code: 2 state graph (merging state 1 into state 3)

class Solution {
    set<string> merge(set<string>&a, set<string>&b){
        if(a.size() == 0){
            return b;
        }
        if(b.size() == 0){
            return a;
        }
        set<string> ans;
        for(auto& v1: a){
            for(auto& v2: b){
                ans.insert(v1+v2);
            }
        }
        return ans;
    }
    //{a,b},{c,d}
    set<string> parseRule2(const string& str, int& i){
        set<string> ans;
        ans = parseRule3(str, i);
        while(i<str.length()){
            if(str[i] != ','){
                break;
            }
            i++;
            set<string> tmp = parseRule3(str, i);
            ans.insert(tmp.begin(), tmp.end());
        }
        return ans;
    }
    //a{c,d}b{e,f}
    set<string> parseRule3(const string& str, int& i){
        set<string> ans;
        while(i < str.length()){
            if(str[i] == '}' || str[i] == ','){
                break;
            }
            if(str[i] == '{'){
                i++;
                set<string> tmp = parseRule2(str, i);
                i++;
                ans = merge(ans, tmp);
            }else{
                set<string> tmp;
                string tmpStr;
                while(i < str.length() && str[i] <= 'z' && str[i] >= 'a'){
                    tmpStr.push_back(str[i++]);
                }
                tmp.insert(tmpStr);
                ans = merge(ans, tmp);
            }
        }
        return ans;
    }
public:
    vector<string> braceExpansionII(string str) {
        int pos = 0;
        set<string> ans = parseRule2(str, pos);
        return vector<string>(ans.begin(), ans.end());
    }
};