Brace Expansion

class Solution {
public:
    vector<vector<char>> charOptions;
    
    void collectCharOptions(string& s) {
        for (int index = 0; index < s.length(); ++index) {
            vector<char> options;
            
            if (s[index] != '{') {
                options.push_back(s[index]);
            } else {
                while (s[index] != '}') {
                    if (s[index] >= 'a' && s[index] <= 'z') {
                        options.push_back(s[index]);
                    }
                    index++;
                }
                sort(options.begin(), options.end());
            }
            
            charOptions.push_back(options);
        }
    }
    
    void createWords(string current, vector<string>& resultWords) {
        if (current.length() == charOptions.size()) {
            resultWords.push_back(current);
            return;
        }
  
        vector<char> options = charOptions[current.length()];

        for (char ch : options) {
            current += ch;
            createWords(current, resultWords);
            current.pop_back();
        }
    }
    
    vector<string> expand(string s) {
        collectCharOptions(s);
        
        vector<string> results;
        createWords("", results);
        return results;
    }
};

This solution outlines a method to expand strings containing sets of characters wrapped in braces ({}) into all possible combinations in lexicographical order. Implemented in C++, this approach involves two main functions: collectCharOptions and createWords, encapsulated within the Solution class.

• Functionality of collectCharOptions:

  • Iterates over each character of the input string.
  • For characters outside braces, adds them directly as an option.
  • For characters within braces, collects all possible characters, sorts them to ensure lexicographical order, and adds the sorted list to charOptions.

• Functionality of createWords:

  • Recursively constructs words by choosing one character at a time from the available options in charOptions.
  • Once a full-length word is constructed (i.e., its length matches charOptions.size()), it is added to the result list.
  • Ensures that all combinations of characters are explored using backtracking.

• Flow of the expand Function:

  • First, call collectCharOptions to parse the input string and organize character options.
  • Initialize an empty list for results.
  • Use createWords starting with an empty current string to generate and collect all possible words.

This method efficiently handles expansion of the combinations by using backtracking, making it adept at generating all possible outcomes for given brace-enclosed strings while maintaining order. These outcomes are then returned as a vector of strings upon calling the expand method with a specific string.

class Processor {
    List<List<Character>> optionsList = new ArrayList<>();

    void collectOptions(String str) {
        for (int indx = 0; indx < str.length(); indx++) {
            List<Character> opts = new ArrayList<>();
            
            if (str.charAt(indx) != '{') {
                opts.add(str.charAt(indx));
            } else {
                while (str.charAt(indx) != '}') {
                    if (str.charAt(indx) >= 'a' && str.charAt(indx) <= 'z') {
                        opts.add(str.charAt(indx));
                    }
                    indx++;
                }
                Collections.sort(opts);
            }
            
            optionsList.add(opts);
        }
    }
    
    void createWords(StringBuilder current, List<String> results) {
        if (current.length() == optionsList.size()) {
            results.add(current.toString());
            return;
        }
        
        List<Character> options = optionsList.get(current.length());
        
        for (char ch : options) {
            current.append(ch);
            createWords(current, results);
            current.deleteCharAt(current.length() - 1);
        }
    }

    public String[] process(String inputString) {
        collectOptions(inputString);
        
        List<String> words = new ArrayList<>();
        createWords(new StringBuilder(), words);
        return words.toArray(new String[0]);
    }
}

The solution provided for the Brace Expansion problem is implemented in Java and involves two main components within the Processor class: collecting possible characters for each position from the input string and generating all possible combinations from these characters.

• The collectOptions method takes a string and parses through each character, detecting groupings enclosed by braces {}. It extracts these options into a list of characters. If a character does not belong to any group, it is added as a singular option.

• For characters within braces, the method extracts only lowercase alphabetical characters, ignoring other characters and sorting the collected characters before adding them to the optionsList.

• The createWords method recursively builds possible words. It uses a depth-first search approach:

  1. If the current building string's length matches the optionsList size, the method adds the built string to the results list and stops further expansion for this branch.

  2. It iterates over the character options available at the current depth, appending each character to a temporary string and recursively calling itself to proceed to the next depth. After exploring one possibility, it removes the last added character to try the next one.

• The process method initializes the process by calling collectOptions with the input string and then createWords to generate all possible combinations.

• The resulting list of combinations is then converted to an array of strings and returned.

This method ensures efficient exploration of all potential combinations by managing options collections systematically and leveraging recursion for combination generation. The approach is particularly suitable for scenarios where input patterns may contain multiple, potentially nested groups of characters that need to be expanded into string combinations according to given rules.