Question

Formatted question description: https://leetcode.ca/all/301.html

 301	Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid.
Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]



Algorithm

Use BFS to solve, put the given string into the queue, and then take it out to check whether it is legal

• If legal, return directly
• If it is illegal, traverse it, and remove the bracket characters to generate a new string for the characters in the left and right brackets encountered
• If this string has not been encountered before, put it in the queue and use HashSet to record whether a string has appeared.

Perform the same operation on each element in the queue, and return to the empty set if no valid string is found until the queue is empty.

Java