Algorithms comparison and complexity
https://softwareengineering.stackexchange.com/questions/336546
-
02-01-2021 - |
Domanda
I want to sole this problem:
Write a method to return all valid combinations of n-pairs of parentheses.
The method should return an ArrayList of strings, in which each string represents a valid combination of parentheses.
The order of the strings in the ArrayList does not matter.
Examples: combParenthesis(2) ==> {"(())","()()"}
Note: Valid combination means that parentheses pairs are not left open. ")()(" is not a valid combination.
My first solution is:
public static ArrayList<String> combParenthesis2(int pairs) {
ArrayList<String> res = new ArrayList<String>();
recursive(pairs, pairs, "", res);
return res;
}
public static void recursive(int left, int right, String build, ArrayList<String> res) {
if(right == 0 && left == 0) {
res.add(build);
return;
}
if(left > 0)
recursive(left-1, right, build + "(", res);
if(right > left)
recursive(left, right-1, build + ")", res);
}
And I think the complexity is O(N^2), am I Wrong?
The second algorithm is:
public static ArrayList<String> combParenthesis(int pairs) {
Set<String> result = new HashSet<>();
if (pairs <= 0) {
return new ArrayList<>(result);
}
result.add("()");
if (pairs == 1) {
return new ArrayList<>(result);
}
for (int i=1; i<pairs; i++) {
Set<String> newSet = new HashSet<>();
for (String s : result) {
newSet.add(s + "()");
newSet.add("()" + s);
newSet.add("(" + s + ")");
}
result = newSet;
}
return new ArrayList<>(result);
}
Which is the complexity of the second algorithm?
Which one do you prefer and why?
Soluzione
I think you are wrong
How did you come to complexity n^2? The complexity of first approach is O(n!) and the algorithm is correct.
Actually the number of valid combinations is C(n), see https://en.wikipedia.org/wiki/Catalan_number, so asymptotically the complexity is O(4^n).
Your second approach has better complexity (O(3^n)) but is incorrect - produces wrong result. For example it wouldn't list "(())(())" in results which is wrong.
So I prefer the first algorithm, because it is correct.