Leetcode 1188 Solution

This article provides solution to leetcode question 1188 (brace-expansion-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 1188" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def braceExpansionII(self, expr: str) -> List[str]:
        i = 0

        def generate(options_list, i, s, ans):
            if i == len(options_list):
                ans.add(s)
                return

            for option in options_list[i]:
                generate(options_list, i + 1, s + option, ans)

        def dfs():
            nonlocal i
            nonlocal expr

            if i == len(expr):
                return set()

            options = []
            while i < len(expr) and expr[i] not in ['}', ',']:
                if expr[i] == '{':
                    i += 1

                    if expr[i] == '}':
                        return set()

                    ans = set()
                    while True:
                        ans |= dfs()

                        if expr[i] == '}':
                            i += 1
                            break
                        elif expr[i] == ',':
                            i += 1
                        else:
                            raise Exception("Unexpected '{}'".format(expr[i]))

                    options.append(ans)
                elif 'a' <= expr[i] <= 'z':
                    options.append({expr[i]})
                    i += 1
                else:
                    raise Exception("Unexpected '{}'".format(expr[i]))

            ans = set()
            generate(options, 0, "", ans)
            return ans

        return sorted(list(dfs()))