This is a follow-up question for the Brace Expansion problem earlier and the only difference is that now, the braces can be nested multiple times.
The main idea is to expand the characters inside the braces and generate new strings. We process this new strings in a queue and subsequently expand further braces until there are no more braces to expand.
class Solution {
public List<String> braceExpansionII(String expression) {
final Deque<String> queue = new ArrayDeque<>();
queue.add(expression);
final Set<String> result = new HashSet<>();
while(!queue.isEmpty()){
String current = queue.poll();
if(current.indexOf("{") == -1){
result.add(current);
continue;
}
// find the boundaries of braces
int right = current.indexOf("}");
int i = right - 1;
while(i >= 0){
if(current.charAt(i--) == '{') break;
}
int left = i + 1;
// extract our options
String[] args = current.substring(left + 1, right).split(",");
// build substrings
for(String s: args){
queue.add(current.substring(0, left) + s + current.substring(right + 1));
}
}
List<String> list = new ArrayList(result);
Collections.sort(list);
return list;
}
}
Runtime: 32 ms, faster than 27.31% of Java online submissions for Brace Expansion II.
Memory Usage: 42.4 MB, less than 100.00% of Java online submissions for Brace Expansion II.