1096. 花括号展开 II

Hard

题目描述

根据下面给出的语法规则，字符串可以表示一组小写单词的集合。设 R(expr) 表示表达式所代表的单词集合。

通过简单的例子可以更好地理解语法规则：

单个字母表示包含该单词的单例集合。
- R(“a”) = {“a”}
- R(“w”) = {“w”}
当我们取两个或多个表达式的逗号分隔列表时，我们取可能性的并集。
- R("{a,b,c}") = {“a”,“b”,“c”}
- R("{{a,b},{b,c}}") = {“a”,“b”,“c”} （注意最终集合中每个单词最多只包含一次）
当我们连接两个表达式时，我们取两个单词之间可能连接的集合，其中第一个单词来自第一个表达式，第二个单词来自第二个表达式。
- 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”}

形式上，我们语法的三个规则是：

对于每个小写字母 x，我们有 R(x) = {x}。
对于表达式 e1, e2, … , ek（k >= 2），我们有 R({e1, e2, …}) = R(e1) ∪ R(e2) ∪ …
对于表达式 e1 和 e2，我们有 R(e1 + e2) = {a + b | (a, b) ∈ R(e1) × R(e2)}，其中 + 表示连接，× 表示笛卡尔积。

给定一个表示根据给定语法的单词集合的表达式，返回表达式表示的单词的排序列表。

示例 1：

输入：expression = "{a,b}{c,{d,e}}"
输出：["ac","ad","ae","bc","bd","be"]

示例 2：

输入：expression = "{{a,z},a{b,c},{ab,z}}"
输出：["a","ab","ac","z"]
解释：每个不同的单词在最终答案中只写一次。

约束：

1 <= expression.length <= 60
expression[i] 由 ‘{’, ‘}’, ‘,’ 或小写英文字母组成。
给定的表达式根据描述中给出的语法表示一组单词。

解题思路

这道题需要解析并计算花括号表达式，主要涉及两种操作：

并集操作：{a,b,c} 表示取 a、b、c 的并集
笛卡尔积操作：相邻表达式表示连接，如 {a,b}{c,d} = {“ac”,“ad”,“bc”,“bd”}

解题思路：

可以采用递归下降解析的方法。我们需要识别两种主要的语法结构：

并集：用逗号分隔的表达式列表，用花括号包围
连接：相邻的表达式直接连接

具体实现步骤：

解析单个块：遇到字母直接返回，遇到 { 则解析到对应的 }
处理并集：在花括号内按逗号分割，递归处理每部分后求并集
处理连接：连续的表达式块进行笛卡尔积连接
去重排序：最终结果需要去重并按字典序排序

算法采用递归解析，每次识别一个完整的表达式块，然后根据上下文决定是进行并集还是连接操作。使用集合数据结构自动处理去重，最后转换为排序列表。

推荐解法：递归下降解析法，清晰地处理语法规则，代码结构良好。

代码实现

class Solution {
private:
    int index;
    
    set<string> parseExpr(const string& expr) {
        set<string> result = parseItem(expr);
        
        while (index < expr.length() && expr[index] != '}' && expr[index] != ',') {
            set<string> next = parseItem(expr);
            set<string> newResult;
            for (const string& s1 : result) {
                for (const string& s2 : next) {
                    newResult.insert(s1 + s2);
                }
            }
            result = newResult;
        }
        
        return result;
    }
    
    set<string> parseItem(const string& expr) {
        set<string> result;
        
        if (expr[index] == '{') {
            index++; // skip '{'
            result = parseExpr(expr);
            
            while (index < expr.length() && expr[index] == ',') {
                index++; // skip ','
                set<string> next = parseExpr(expr);
                result.insert(next.begin(), next.end());
            }
            
            index++; // skip '}'
        } else {
            result.insert(string(1, expr[index]));
            index++;
        }
        
        return result;
    }
    
public:
    vector<string> braceExpansionII(string expression) {
        index = 0;
        set<string> resultSet = parseExpr(expression);
        return vector<string>(resultSet.begin(), resultSet.end());
    }
};

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def parse_expr():
            result = parse_item()
            
            while self.index < len(expression) and expression[self.index] not in '}':
                if expression[self.index] == ',':
                    break
                next_set = parse_item()
                new_result = set()
                for s1 in result:
                    for s2 in next_set:
                        new_result.add(s1 + s2)
                result = new_result
            
            return result
        
        def parse_item():
            result = set()
            
            if expression[self.index] == '{':
                self.index += 1  # skip '{'
                result = parse_expr()
                
                while self.index < len(expression) and expression[self.index] == ',':
                    self.index += 1  # skip ','
                    next_set = parse_expr()
                    result.update(next_set)
                
                self.index += 1  # skip '}'
            else:
                result.add(expression[self.index])
                self.index += 1
            
            return result
        
        self.index = 0
        result_set = parse_expr()
        return sorted(list(result_set))

public class Solution {
    private int index;
    
    public IList<string> BraceExpansionII(string expression) {
        index = 0;
        var resultSet = ParseExpr(expression);
        var result = new List<string>(resultSet);
        result.Sort();
        return result;
    }
    
    private HashSet<string> ParseExpr(string expr) {
        var result = ParseItem(expr);
        
        while (index < expr.Length && expr[index] != '}' && expr[index] != ',') {
            var next = ParseItem(expr);
            var newResult = new HashSet<string>();
            foreach (var s1 in result) {
                foreach (var s2 in next) {
                    newResult.Add(s1 + s2);
                }
            }
            result = newResult;
        }
        
        return result;
    }
    
    private HashSet<string> ParseItem(string expr) {
        var result = new HashSet<string>();
        
        if (expr[index] == '{') {
            index++; // skip '{'
            result = ParseExpr(expr);
            
            while (index < expr.Length && expr[index] == ',') {
                index++; // skip ','
                var next = ParseExpr(expr);
                foreach (var item in next) {
                    result.Add(item);
                }
            }
            
            index++; // skip '}'
        } else {
            result.Add(expr[index].ToString());
            index++;
        }
        
        return result;
    }
}

var braceExpansionII = function(expression) {
    let index = 0;
    
    function parseExpr() {
        let result = parseItem();
        
        while (index < expression.length && expression[index] !== '}' && expression[index] !== ',') {
            let next = parseItem();
            let newResult = new Set();
            for (let s1 of result) {
                for (let s2 of next) {
                    newResult.add(s1 + s2);
                }
            }
            result = newResult;
        }
        
        return result;
    }
    
    function parseItem() {
        let result = new Set();
        
        if (expression[index]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(N × M)	N 是表达式长度，M 是最终结果集的大小。在最坏情况下需要生成所有可能的字符串组合
空间复杂度	O(M)	M 是最终结果集的大小，用于存储所有可能的字符串

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目