Title:
Generate Well-Formed Parenthesese of Length N
Link to LeetCode:
https://leetcode.com/problems/generate-parentheses/
Specification:
Given n pairs of parentheses,
write a function to generate all combinations of well-formed parentheses.
Examples:
Example 1:
Input: n = 3
Output: [
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Initial Code and Signature:
import java.util.List;
public interface ParenthesesGenerator {
public List generateParenthesis(int n);
}
Algorithm:
Run-Time Analysis:
GitHub Project:
Code:
import java.util.*;
/**
*
* @author Mahsa Sadi
*
* @since 2020-02-26
*
* License: Creative Commons
*
* Copyright by Mahsa Sadi
*
*/
public class ParenthesesGeneratorV1 implements ParenthesesGenerator {
/**
*
* Problem: Generate Parentheses
*
*
* Description:
*
* Given n pairs of parentheses,
* write a function to generate all combinations of well-formed parentheses.
*
*
*
* Solution:
*
* 1- list of all valid sentences with length N = {};
*
* 2- counter = 0;
*
* 3- counter ++;
*
* 4- Open Parenthesis.
*
* 5- max number of allowed close parenthesis ++;
*
*
* 6- for i = 0 to max number number of valid close parenthesis
*
* 6-1 Close Parenthesis for i times.
* 6-2 Repeat (Go to 3-) if counter != N
*
*
* 7 - Add generated sentence to the list of valid sentences if length of sentence = N * 2;
*
*
*/
List validSentences;
int numberOfPairs;
final String OpenTerm = "(" ;
final String CloseTerm = ")";
public List generateParenthesis(int n) {
validSentences = new ArrayList ();
numberOfPairs = n;
generateSentence ("", 0, 0);
return validSentences;
}
public void generateSentence (String sentence, int counter, int maxNumberofValidCloseTerms)
{
if (counter == numberOfPairs)
{
if ( sentence.length() == numberOfPairs * 2 )
validSentences.add(sentence);
}
else
{
counter++;
sentence += OpenTerm;
maxNumberofValidCloseTerms ++;
for (int i = 0; i <= maxNumberofValidCloseTerms; i++)
generateSentence (sentence + CloseTerm.repeat (i), counter, (maxNumberofValidCloseTerms - i));
}
}
}