花括号展开 II

标签: 栈 广度优先搜索 字符串 回溯

难度: Hard

如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。

花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串，定义下面几条语法规则：

  • 如果只给出单一的元素 x，那么表达式表示的字符串就只有 "x"。R(x) = {x}
    • 例如，表达式 "a" 表示字符串 "a"。
    • 而表达式 "w" 就表示字符串 "w"。
  • 当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
    • 例如，表达式 "{a,b,c}" 表示字符串 "a","b","c"。
    • 而表达式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"。
  • 要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
    • 例如，表达式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"。
  • 表达式之间允许嵌套，单一元素与表达式的连接也是允许的。
    • 例如，表达式 "a{b,c,d}" 表示字符串 "ab","ac","ad"​​​​​​。
    • 例如，表达式 "a{b,c}{d,e}f{g,h}" 可以表示字符串 "abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"。

给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。

假如你希望以「集合」的概念了解此题，也可以通过点击 “显示英文描述” 获取详情。

示例 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] 由 '{'，'}'，',' 或小写英文字母组成
  • 给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串

Submission

运行时间: 32 ms

内存: 0.0 MB

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 c == ',' and level == 0:
                groups.append([])
            elif level == 0:
                groups[-1].append([c])
        word_set = set()
        for group in groups:
            word_set |= set(map(''.join, itertools.product(*group)))
        return sorted(word_set)
    
    
        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 c == ',' and level == 0:
                groups.append([])
            elif level == 0:
                groups[-1].append([c])
        word_set = set()
        for group in groups:
            word_set |= set(map(''.join, itertools.product(*group)))
        return sorted(word_set)

Explain

本题解采用递归与分治的方法来处理花括号表达式的展开。首先，通过遍历输入字符串，使用一个栈结构来处理花括号的嵌套。遇到'{'时，增加嵌套级别；遇到'}'时，减少嵌套级别。当嵌套级别为0时，表示当前读到的字符属于最外层。使用一个列表`groups`来存储当前层级的字符串或子表达式的列表。如果遇到逗号','且处于最外层，将开始一个新的子表达式组。当遇到'}'且嵌套级别回到0时，递归处理这部分子表达式。对于每一个最外层的表达式组，使用`itertools.product`来生成所有可能的字符串组合，然后通过集合去重。最后，将结果排序后返回。

时间复杂度: O(2^n)（n 是表达式长度，指数级复杂度是假设每个表达式都可能引发大量的字符串组合生成）

空间复杂度: O(n^2)（n 是表达式的长度，考虑到递归的深度和每层可能存储的元素数量）

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 c == ',' and level == 0:
                groups.append([])
            elif level == 0:
                groups[-1].append([c])  # 处理单个字符作为一个组
        word_set = set()  # 用于存储所有唯一的组合结果
        for group in groups:
            word_set |= set(map(''.join, itertools.product(*group)))  # 生成所有可能的字符串组合
        return sorted(word_set)  # 返回排序后的结果

Explore

使用栈来管理嵌套级别的主要优势在于其能够自然地处理嵌套结构和匹配的开闭花括号，这是因为栈是一种后进先出（LIFO）的数据结构。在解析具有层次结构的表达式时，栈可以帮助我们记录当前的嵌套深度和回溯到先前的状态。每当遇到一个开花括号'{'，我们就推入栈增加嵌套层级，遇到闭花括号'}'时，栈弹出帮助我们恢复到上一层，从而有效地处理和构建每一层的表达式内容。

使用`itertools.product`可以高效地生成所有可能的字符串组合，因为它是专为笛卡尔积设计的。然而，当输入数据包含大量元素和组合时，生成的组合数量将呈指数增长，这可能导致内存使用高昂甚至耗尽内存，从而成为性能瓶颈。在实际应用中，需要注意输入大小和结果集的可管理性，有时可能需要优化或限制输入规模以避免低效运算。

题解中的代码没有特别处理连续的逗号或者不平衡的花括号，这可能导致运行时错误或者意外的行为。在实际应用中，应该添加错误检测和处理逻辑来识别这些情况。例如，可以在解析时检查连续的逗号并跳过，或者在发现不平衡的花括号时抛出异常或进行错误处理。这需要额外的代码来增强鲁棒性和错误处理能力。