Problem 16.6 Solution?

#1

The solution to generate matching strings proposes to count the number of lefts and number of rights and to play around with that, but I really don’t understand why that is necessary.

We know that a balanced string has to have opening & closing parenthesis. Why not start from a bottom-up approach and build it in this way: Generating 3 strings from the current string every time:
1 - “(” + currentString + ")"
2 - “()” + currentString
3 - currentString + "()"
with the base case being checking string length / 2 == n.

The solution I came up with was (in code):

generateParens(int n, String /*or StringBuilder */ currentString, List<String> resultsList) { if ((currentString.length() / 2) == n) { resultsList.add(currentString /* or currentStringB.toString()) */); //strings being immutable, no need to worry about copying } else { //using stringbuilder here avoids needlessly re-copying => only recopy when base case //add "()" to begining. generateParens(n, /* "()" + */ currentString, resultsList); //remove "()" from begining, and add "() to end generateParens(n, currentString /* + "()" */, resultsList); //remove "()" from end, and add "(" at beginning & ")" at end. generateParens(n, /* "(" + */ currentString /* + ")" */ ,resultsList); //remove first & last elements. }

Tried analyzing time complexity (ignoring stringbuilder):
T(n) = aT(n-b) + O(n^d) with d=1 (being the copy operation of string), a = 3 (3 calls) and b = 2. (Since the size grows by 2 elements every time)

Came up with T(n) = (n*3^n/2).

0 Likes
#2

Hey @jowpellet,

Very good idea but I wonder how you remove the duplication issues generating from 2 and 3 assuming currentString is like “” or “()”?

From the code, I think your algorithm will generate the duplicate answers from that.

0 Likes
#3

To avoid the duplicates why not using something like a hash_set (i.e unordered_set in c++) for the resultList ?

0 Likes
#4

However It seems that the solution proposed here will not be able to generate some of the correct strings like: ‘(())(())’ (in case of n=4) which can’t be constructed using the 3 scenarios (1 - “(” + currentString + “)” 2 - “()” + currentString 3 - currentString + “()”) .

1 Like
#5

You can use hash_set to prevent the duplication problem but it is not needed if you implement your algorithm correctly.

0 Likes