mosh111
BAN USER- 0of 0 votes
AnswersImplement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.
- mosh111 in United States
EXAMPLE:
input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))
This question is from "Cracking the coding interview" (Fourth Edition) and I think that I found mistake in the answer.| Report Duplicate | Flag | PURGE
CareerCup Software Engineer / Developer Algorithm
- 1 Answer print all validate parentheses - found mistake in the book
This question is from "Cracking the coding interview" (Fourth Edition) and I think that I found mistake in the answer.
let's take n=3 in the book example you get 4 sequences, but I think there is 5 sequences. ((())), ()(()), ()()(), (()()), (())()
also my solution is much more simple from that in the book
- mosh111 July 16, 2014public static ArrayList<String> GetAllNPairsOfParentheses(int n) { ArrayList<String> retArray; if (n==1) { retArray=new ArrayList<String>(); retArray.add("()"); return retArray; } retArray= GetAllNPairsOfParentheses(n-1); HashSet<String> hash=new HashSet<String>(); for (String currentPrantheses : retArray) { for (int i=0;i<currentPrantheses.length();i++) { String currentPranthesesBegin = currentPrantheses.substring(0,i); String currentPranthesesEnd = currentPrantheses.substring(i); String newPrantheses= currentPranthesesBegin+"()"+currentPranthesesEnd; if (!hash.contains(newPrantheses)) { hash.add(newPrantheses); } } } retArray=new ArrayList<String>(); for (String currentPrantheses : hash) { retArray.add(currentPrantheses); } return retArray; }
| Flag | PURGE
let's take n=3 in the book example you get 4 sequences, but I think there is 5 sequences. ((())), ()(()), ()()(), (()()), (())()
also my solution is much more simple from that in the book
- mosh111 July 16, 2014