Concise code in Java


  • 3
    Z

    My thought: To confirm to the limitation, we can construct a stack mentally. A '(' corresponds to push, while a ')' corresponds to pop. At this point, our mission is to push all '('s in to the stack and pop the stack until it's empty. Of course, the operations can interleave. I took a recursive way since it's straight forward that at each state, say m '(' waiting to be pushed and n '(' waiting to be popped, we can either push a '(' or pop a '('.

    public class Solution {
        
        List<String> ans = new ArrayList<String>();
        
        public List<String> generateParenthesis(int n) {
            dp(n, 0, "");
            return ans;
        }
        
        public void dp(int outstack, int instack, String res) {
            if(outstack == 0 && instack == 0) {
                ans.add(res);
                return;
            }
            if(outstack > 0) {
                dp(outstack-1, instack+1, res+"(");
            } 
            if(instack > 0) {
                dp(outstack, instack-1, res+")");
            }
            return;
        }
        
    }
    

    However, I don't have a clue how to implement it iteratively :(


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    Z

    Thank you for your advice and link, with my question updated.


  • 0
    S

    This wiki: https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics can provide you a iterative thought.


  • 0
    S

    Here is my iteratively solution. Based on Applications of Catalan Number in combinatorics

    public class Solution {
    private static final String UNIT = "()";
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if (n == 0) return result;
        Set<String> visited = new HashSet<String>();
        Queue<String> queue = new ArrayDeque<String>();
        queue.add(UNIT);
        visited.add(UNIT);
        while (!queue.isEmpty()) {
            String s = queue.poll();
            if (s.length() == n * 2)
                result.add(s);
            else {
                for (int i = 0; i <= s.length() / 2; i++) {
                    String news = s.substring(0, i) + UNIT + s.substring(i, s.length());
                    if (!visited.contains(news)) {
                        visited.add(news);
                        queue.add(news);
                    }
                }
            }
        }
        return result;
    }
    }
    

Log in to reply
 

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