Leetcode 1188 Solution
This article provides solution to leetcode question 1188 (brace-expansion-ii)
Access this page by simply typing in "lcs 1188" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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()))