_1087. Brace Expansion.md

1087. Brace Expansion

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 15, 2024

Last updated : June 15, 2024

---

Related Topics : String, Backtracking, Breadth-First Search

Acceptance Rate : 66.401 %

---

Solutions

• m1087 v1 sort after combinations.py
• m1087 v2 sort before combinations.py

Python

m1087 v1 sort after combinations.py

class Solution:
    def expand(self, s: str) -> List[str]:
        outputs = []

        currentlyInBrace = False
        for c in s :
            if not currentlyInBrace :
                if c == '{' :
                    currentlyInBrace = True
                    outputs.append([])
                else:
                    outputs.append(c)
            else :
                if c == '}' :
                    currentlyInBrace = False
                elif c != ',' :
                    outputs[-1].append(c)

        outputStrings = []
        helperOutput = []

        def helper(currIndx: int) -> None :
            if currIndx >= len(outputs) :
                outputStrings.append(''.join(helperOutput))
                return

            if isinstance(outputs[currIndx], str) :
                helperOutput.append(outputs[currIndx])
                helper(currIndx + 1)
                helperOutput.pop()
            else :
                for c in outputs[currIndx] :
                    helperOutput.append(c)
                    helper(currIndx + 1)
                    helperOutput.pop()
        helper(0)
        return sorted(outputStrings)

m1087 v2 sort before combinations.py

class Solution:
    def expand(self, s: str) -> List[str]:
        outputs = []

        currentlyInBrace = False
        for c in s :
            if not currentlyInBrace :
                if c == '{' :
                    currentlyInBrace = True
                    outputs.append([])
                else:
                    outputs.append(c)
            else :
                if c == '}' :
                    outputs[-1].sort()
                    currentlyInBrace = False
                elif c != ',' :
                    outputs[-1].append(c)

        outputStrings = []
        helperOutput = []

        def helper(currIndx: int) -> None :
            if currIndx >= len(outputs) :
                outputStrings.append(''.join(helperOutput))
                return

            if isinstance(outputs[currIndx], str) :
                helperOutput.append(outputs[currIndx])
                helper(currIndx + 1)
                helperOutput.pop()
            else :
                for c in outputs[currIndx] :
                    helperOutput.append(c)
                    helper(currIndx + 1)
                    helperOutput.pop()
        helper(0)
        return outputStrings