All Vaid Permutation of Parentheses¶
Get all valid permutations of l pairs of (), m pairs of <> and n pairs of {}, subject to the priority restriction: {} higher than <> higher than ().
Assumptions
l, m, n >= 0
l + m + n >= 0
Examples
l = 1, m = 1, n = 0, all the valid permutations are ["()<>", "<()>", "<>()"].
l = 2, m = 0, n = 1, all the valid permutations are [“()(){}”, “(){()}”, “(){}()”, “{()()}”, “{()}()”, “{}()()”].
Analysis¶
Use a stack to preserve the priority (lower index means lower priority, and higher priority parenthese should surround the lower priority parenthese).
- check if is open parenthese
- if yes, check if is enclosed by higher priority (or empty) and push into the stack
- if no, check if previous one is the corresponding open parenthese and delete the previous open parenthese index from stack
Java Code¶
public class Solution {
private static final char[] PS = new char[]{'(', ')', '<', '>', '{', '}'};
public List<String> validParenthesesIII(int l, int m, int n) {
int[] remain = new int[]{l, l, m, m, n, n};
int targetLen = 2 * l + 2 * m + 2 * n;
StringBuilder cur = new StringBuilder();
Deque<Integer> stack = new LinkedList<Integer>();
List<String> result = new ArrayList<String>();
helper(cur, stack, remain, targetLen, result);
return result;
}
private void helper(StringBuilder cur, Deque<Integer> stack, int[] remain,
int targetLen, List<String> result) {
// need to use all parentheses
if (cur.length() == targetLen) {
result.add(cur.toString());
return;
}
for (int i = 0; i < remain.length; ++i) {
if (i % 2 == 0) { // ( < or {
// top of stack has a lower priority -> need to be surrounded by higher priority parenthese
if (remain[i] > 0 && (stack.isEmpty() || stack.peekFirst() > i)) {
cur.append(PS[i]);
stack.offerFirst(i);
remain[i]--;
helper(cur, stack, remain, targetLen, result);
cur.deleteCharAt(cur.length() - 1);
stack.pollFirst();
remain[i]++;
}
} else { // ) > or }
// only update the cur if previous / top of the stack is the corresponding open parentheses
if (!stack.isEmpty() && stack.peekFirst() == i - 1) {
cur.append(PS[i]);
stack.pollFirst();
remain[i]--;
helper(cur, stack, remain, targetLen, result);
cur.deleteCharAt(cur.length() - 1);
stack.offerFirst(i - 1);
remain[i]++;
}
}
}
}
}
Last update:
October 29, 2020