Accepted non-recursive Java solution.


  • 1
    P

    Please see comments.

    public List<String> generateParenthesis(int n) {
    	
        List<String> result = new ArrayList<String>();
        
        int i = 0;
        int open = n-1;
        int closed = n;
        char[] chars = new char[n*2+1];
        chars[i++] = chars[i++] = '(';
        
        while (chars[0] == '(') {
        	if (open > 0) {
        		chars[i++] = '(';
        		open-- ;
        	} else if (closed > 0 && open < closed) {
        		chars[i++] = ')';
        		closed-- ;
        	} else {
        		// Save result
        		result.add(new String(chars, 1, n*2));
        		
        		// Find next open parenthesis which is possible
        		// to replace with closed parenthesis
        		while ((chars[--i] == ')' || (chars[i] == '(' && closed - open == 1))) {
        			if (chars[i] == ')') {
        				closed++;
        			} else {
        				open++;
        			}
        		}
    			chars[i++] = ')';
        		closed--;
        		open++;
        	}
        }
        
        return result;
    }

  • 0
    Q

    Could you please give more specific explanation of your solution?


  • 0
    P

    What exactly do you need to be explained?


Log in to reply
 

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