LeetCode 1087. Brace Expansion

Description

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

You are given a string s representing a list of words. Each letter in the word has one or more options.

• If there is one option, the letter is represented as is.
• If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "a{b,c}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"].

Return all words that can be formed in this manner, sorted in lexicographical order.

Example 1:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Constraints:

• 1 <= s.length <= 50
• s consists of curly brackets '{}', commas ',', and lowercase English letters.
• s is guaranteed to be a valid input.
• There are no nested curly brackets.
• All characters inside a pair of consecutive opening and ending curly brackets are different.

Explanation

The goal of the problem is to find all combination strings. Whenever we encounter a ‘{‘, we can build combinations from different options, after that, we go to the character after ‘}’ to continue building combinations. When we encounter a letter, we just go to the next character in the string. In the end, sort the results in alphabetically ascending order.

Python Solution

class Solution:
    def expand(self, s: str) -> List[str]:
        results = []
        
        end = len(s)
        
        self.helper(results, "", 0, s)
        
        results = sorted(results)
        
        return results
                
    def helper(self, results, combination, start, s):        
        if start == len(s):
            results.append(combination)
            return
        
        i = start
        
        if s[i] == '{':
            j = i + 1            
            
            options = []

            while s[j] != '}':
                if s[j] != ',':
                    options.append(s[j])
                j += 1
            
            for option in options:                
                self.helper(results, combination + option, j + 1, s)

        elif s[i] == '}':
            return
        
        else:                
            self.helper(results, combination + s[i], i + 1, s)