I did a problem of returning valid parentheses strings from a given pair of parentheses. Eg. if n=2, I must return a list of valid sequences i.e ["()()", "(())"]. If the question is not very clear, need not worry because my doubt is more generic.
I used dynamic programming to find solution. The list(list) stores list of valid sequences for any pair k. The list(lists) stores all such lists from 0<=k<=n. I went for two approaches with very minor change. Soln 1 -
public List<String> generateParenthesis(int n) {
List<List<String>> lists = new ArrayList<>();
lists.add(Collections.singletonList(""));
for (int i=1; i<=n; i++) {
List<String> list = new ArrayList<>();
for (int j=0; j<i; j++) {
for (String first : lists.get(j)) {
for (String second : lists.get(i-1-j))
list.add("(" + first + ")" +second);
}
}
lists.add(list);
}
return lists.get(lists.size()-1);
Soln 2-
public List<String> generateParenthesis(int n) {
List<List<String>> lists = new ArrayList<>();
lists.add(Collections.singletonList(""));
for (int i=1; i<=n; i++) {
List<String> list = new LinkedList<>();
for (int j=0; j<i; j++) {
for (String first : lists.get(j)) {
for (String second : lists.get(i-1-j))
list.add("(" + first + ")" +second);
}
}
lists.add(list);
}
return lists.get(lists.size()-1);
The only difference between them is that list(list) is ArrayList in first case and LinkedList in second. As per their API description on oracle site, for both implementations the add operation takes constant time and the constant factor for ArrayList is low as compared to LinkedList implementation. I expected my first soln to be faster but actually it is the second one.
PS - I attempted the question on leetcode, so they have a list of sample test cases for 1<=n<=8.
Can someone please explain the reason?
