Brace Expansion II LeetCode solution in Python

1
class Solution:
2
    def braceExpansionII(self, expression: str) -> List[str]:
3
        s = list(reversed("{" + expression + "}"))
4

5
        def full_word():
6
            cur = []
7
            while s and s[-1].isalpha():
8
                cur.append(s.pop())
9
            return "".join(cur)
10

11
        def _expr():
12
            res = set()
13
            if s[-1].isalpha():
14
                res.add(full_word())
15
            elif s[-1] == "{":
16
                s.pop()  # remove open brace
17
                res.update(_expr())
18
                while s and s[-1] == ",":
19
                    s.pop()  # remove comma
20
                    res.update(_expr())
21
                s.pop()  # remove close brace
22
            while s and s[-1] not in "},":
23
                res = {e + o for o in _expr() for e in res}
24
            return res
25

26
        return sorted(_expr())