class Solution:
def expand(self, s: str) -> List[str]:
candidates = []
i = 0
while i < len(s):
if s[i] == '{':
j = i
while j < len(s):
if s[j] == '}':
break
j += 1
candidates.append(s[i+1:j].split(','))
i = j
else:
candidates.append([s[i]])
i += 1
n = len(candidates)
ans = []
def backtrack(curr, index):
if len(curr) == n:
ans.append(''.join(list(curr)))
return
else:
arr = candidates[index]
for char in arr:
curr.append(char)
backtrack(curr, index + 1)
curr.pop()
backtrack([], 0)
ans.sort()
return ans