花括号展开

Submission

运行时间: 26 ms

内存: 16.5 MB

class Solution:
    def expand(self, s: str) -> List[str]:
        arr = []
        flagIn = False
        for c in s:
            if c == "{":
                flagIn = True
                arr.append("")
            elif c.isalpha():
                if flagIn:
                    arr[-1] += c
                else:
                    arr.append(c)
            elif c == '}':
                flagIn = False
        res = []
        s = [""]*len(arr)

        def dfs(x):
            if x == len(arr):
                res.append("".join(s))
                return
            for c in arr[x]:
                s[x] = c
                dfs(x+1)
        
        dfs(0)
        return sorted(res)

Explain

该题解采用了深度优先搜索（DFS）来解决花括号展开问题。首先，遍历输入字符串，按照花括号内外的字符分组，并存储到数组arr中。数组中的每个元素要么是花括号内的一组字符，要么是花括号外的单个字符。利用DFS遍历arr数组中的每个元素，构建所有可能的字符串组合。最后，返回排序后的结果列表。

时间复杂度: O(n * k^n)

空间复杂度: O(n + k^n)

class Solution:
    def expand(self, s: str) -> List[str]:
        arr = []  # 存储分组后的字符或字符集
        flagIn = False  # 标志是否在花括号内部
        for c in s:
            if c == '{':
                flagIn = True
                arr.append('')  # 开始新的花括号内组
            elif c.isalpha():
                if flagIn:
                    arr[-1] += c  # 花括号内部，添加字符到当前组
                else:
                    arr.append(c)  # 花括号外部，直接作为独立组
            elif c == '}':
                flagIn = False  # 结束当前花括号内组
        res = []  # 最终结果列表
        s = ['']*len(arr)  # 用于存储当前的字符串构建状态

        def dfs(x):
            if x == len(arr):
                res.append(''.join(s))  # 完成一种组合，添加到结果中
                return
            for c in arr[x]:
                s[x] = c  # 选择当前位置的一个字符，进行递归
                dfs(x+1)
        
        dfs(0)  # 从第一个组开始递归
        return sorted(res)  # 返回排序后的结果

Explore

DFS是适合这类问题的，因为它能够通过递归的方式自然地处理嵌套结构，例如花括号中的内容。DFS可以直接对每个字符或字符集进行递归分支，便于构建和追踪不同的字符串组合。相比之下，BFS和迭代方法虽然也可以实现，但在处理深度嵌套或多层分支时，管理和构建这些组合的复杂度会显著增加。DFS通过递归调用自身，更直观地反映了组合的构建过程。

在题解的实现中，连续的花括号外字符应当作为整个单元存储在数组arr中。例如，'ab'和'e'都应当被视为独立的元素。处理过程中，若遇到花括号外的字符并且不是在花括号内，则这些连续字符应连续累加直到遇到下一个花括号或字符串结束。这在题解中未明确说明，是一个需要改进的地方。正确的处理应当在读取到第一个花括号外的字符时开始一个新的元素，并继续添加到该元素直到遇到花括号或字符串结束。

在DFS递归函数中，每次递归都会遍历当前位置的字符集中的每一个字符。通过循环遍历arr数组中的每个元素，并在每个循环中递归调用DFS函数，确保从每个字符集选择一个字符进行组合。这样的循环确保了每个字符都有机会被选中，并且每种可能的字符串组合都被构建和记录。

在递归过程中，栈溢出是可能发生的，尤其是在处理非常长的字符串或深度嵌套的花括号时。每次递归调用都会使用栈空间，如果递归层数过多，可能会导致栈溢出错误。特别是在输入字符串中花括号嵌套层数非常高或字符串长度过长时，每增加一层嵌套或一个字符，都会相应地增加调用栈的深度。优化递归深度或改用迭代方法可以减少这种风险。