Java Solution (8 ms) using HashSet


  • 2
    A

    I won't claim that this is efficient, but it does run a lot faster than I expected it to. I was having trouble coming up with a better recursive solution, so I did this: for each pattern of (n-1) parenthesis, insert an "()" at each position and each new pattern to a HashSet. If the pattern was already in the HashSet, ignore it and continue.

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n <= 0) return result;
        if(n == 1) {result.add("()"); return result;}
        StringBuilder sb = new StringBuilder();
        HashSet<String> hashSet = new HashSet<>();
        List<String> prev = generateParenthesis(n-1);
        for(String s : prev) {
            for(int i = 0; i <= s.length(); i++) {
                sb.setLength(0);
                sb.append(s);
                sb.insert(i, "()");
                if(!hashSet.contains(sb.toString())) {
                    result.add(sb.toString());
                    hashSet.add(sb.toString());
                } 
            }
        }
        return result;
    }

  • 0

    Similar thought except I do it iteratively. For your reference: https://discuss.leetcode.com/topic/55984/very-easy-iterative-java-solution-using-set


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.