[LeetCode] 1096. Brace Expansion II

[grandyang]

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_1 and 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 expression representing 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 <= 60
2. expression[i] consists of '{', '}', ','or lowercase English letters.
3. The given expression represents a set of words based on the grammar given in the description.

这道题定义了一些花括号的展开规则，比如逗号隔开的就是并列的关系，若字母和括号直接相连，则用字母乘以里面的每一项。若两个花括号相连，则里面的内容交叉相乘，有点像乘法的分配律的感觉。现在给了一个花括号的表达式，让我们进行展开，并把最终的结果进行排序。由于这道题里面可能会有多重花括号嵌套，所以展开的顺序应该是从内到外，就像是递归的思路一样，先进到最里面，把最内层的处理完了之后，再回溯出来一层一层的处理，直到所有的花括号都完全展开。这里使用一个栈 stack 来模拟这个递归的过程，将给定的表达式 expression 先加进栈，还需要一个 HashSet 来避免重复的结果，然后进行 while 循环，条件是栈不为空。在循环中，取出栈顶元素，首先查找左花括号，若不存在的话，说明当前的表达式没有花括号了，不需要进一步展开了，再检查一下，假如 visited 中不存在，则加入其中，并且加入到结果 res 中。若包含左花括号，则此时需要进一步操作，需要找到最内层的花括号，方法是用一个 while 循环，只要当前位置不是右花括号则进行循环，在循环中，若遇到左花括号，则进行标记，由于遇到下一个右花括号就直接退出循环了，若遇到新的左花括号则 left 也会被更新，这样就保证了标记范围内不会再有左花括号。然后根据标记的左右花括号的位置，将左右两边的部分也提取出来，中间虽然没有其他花括号了，但是还可能有逗号，所以需要拆分所有的逗号分隔的字符串，由于 C++ 中没有 Java 的 split 函数，只能用字符串流类 istringstream 来老老实实的进行分隔逗号了，将分隔出来的部分左右分别加上 before 和 after，再压入栈中等待下一次循环即可，进行相同的操作直至所有的花括号均被展开。最后别忘了给结果 res 中的字符串进行排序，参见代码如下：

class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        vector<string> res;
        unordered_set<string> visited;
        stack<string> stk;
        stk.push(expression);
        while (!stk.empty()) {
            string str = stk.top(); stk.pop();
            if (str.find("{") == string::npos) {
                if (!visited.count(str)) {
                    visited.insert(str);
                    res.push_back(str);
                }
                continue;
            }
            int i = 0, left = 0, right = 0;
            while (str[i] != '}') {
                if (str[i++] == '{') left = i - 1;
            }
            right = i;
            string before = str.substr(0, left);
            string after = str.substr(right + 1);
            string mid = str.substr(left + 1, right - left - 1);
            istringstream iss(mid);
            string t;
            while (getline(iss, t, ',')) {
                stk.push(before + t + after);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

Github 同步地址:

#1096

类似题目：

Brace Expansion

参考资料：

https://leetcode.com/problems/brace-expansion-ii/

https://leetcode.com/problems/brace-expansion-ii/discuss/348541/JAVA-iter_dfs-36ms

https://leetcode.com/problems/brace-expansion-ii/discuss/317890/Simple-solution-(C%2B%2B)

LeetCode All in One 题目讲解汇总(持续更新中...)