D
DevExCode

LeetCode 1096: Brace Expansion II Solution

Master LeetCode problem 1096 (Brace Expansion II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use recursion and iterate through the given expression to parse it according to the grammar rules provided. We will handle the three cases: single letters, union of expressions, and concatenation of expressions.

  1. For single letters, we add the letter to the result set.
  2. For union of expressions, we recursively parse each expression and take the union of the results.
  3. For concatenation of expressions, we recursively parse each expression and generate the cartesian product of the results.

We use a set to store the intermediate results and then convert it to a sorted list before returning the final answer.

Time Complexity: The time complexity of this approach is exponential, as we generate all possible combinations of the expressions.

Space Complexity: The space complexity is also exponential due to the number of possible combinations generated.

Solution Code

class Solution {
    public List<String> braceExpansionII(String expression) {
        Set<String> result = parse(expression);
        List<String> resList = new ArrayList<>(result);
        Collections.sort(resList);
        return resList;
    }

    private Set<String> parse(String expression) {
        Set<String> result = new HashSet<>();

        if (expression.charAt(0) != '{') {
            result.add(String.valueOf(expression.charAt(0)));
            return result;
        }

        int count = 0;
        int start = 0;

        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '{') {
                count++;
            } else if (expression.charAt(i) == '}') {
                count--;
            }

            if (count == 0 && i != expression.length() - 1) {
                if (expression.charAt(i + 1) == ',') {
                    result.addAll(parse(expression.substring(start + 1, i)));
                    start = i + 1;
                } else if (expression.charAt(i + 1) == '{' || i + 1 == expression.length() - 1) {
                    result.addAll(cartesianProduct(parse(expression.substring(start + 1, i)), parse(expression.substring(i + 2, expression.length() - 1)));
                    break;
                }
            }
        }

        return result;
    }

    private Set<String> cartesianProduct(Set<String> set1, Set<String> set2) {
        Set<String> result = new HashSet<>();
        for (String s1 : set1) {
            for (String s2 : set2) {
                result.add(s1 + s2);
            }
        }
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1096 (Brace Expansion II)?

This page provides optimized solutions for LeetCode problem 1096 (Brace Expansion II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1096 (Brace Expansion II)?

The time complexity for LeetCode 1096 (Brace Expansion II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1096 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1096 in Java, C++, or Python.

Back to LeetCode Solutions