June 23, 2020
301 remove minimum invalid parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
How to study a solution written in BFS?
I did learn the idea back in 2018. After two years, I learned and value the case study method.
It is important for me to write down a few simple test cases first, and then go over one by one to explain to myself first, how to apply BFS and make it work.
Case study approach from Harvard business school teaching is my favorite learning technique now.
I like to study the BFS solution again written in Java. The link is
here.
2020 June 23 - review BFS solution
I plan to write a C# solution using the same idea. I will write a case study to explain how to approach the problem.
I spent a few hours to write a solution on June 22, 2020,
here is the link.
I debugged the code using string "())" step by step, it is hard for me to understand the design. So I decide to remove pruning part, focus on basic BFS algorithm. Keep minimum to solve the problem first using BFS.
I decided to continue to remove those code hard to understand, in other words, make it work for Leetcode online judge, remove those pruning ideas first.
Case study
I think that it is important to go over test cases and then talk about how to solve the problem. The following is to go over valid string, remove one parenthese, two parentheses three test cases.
Case study 1: "()", or any valid string
The string is valid, so first step in my design is to check original string is valid or not.
If it is, then return original string. Othewise at least one parenthese should be removed.
Case study 2: Remove one parentheses
For example "())", minimum number of invalid parentheses is 1, result is "()".
"(()"
How to design using BFS algorithm, using Queue to help.
Remove one char from index = 0 to last one, and see if the substring is valid or not.
index = 0, "))", not valid
index = 1, "()", valid
index = 2, "()", valid
The way to skip the duplicate valid string is to save in the hashset first, and then convert set to List object.
Rule 1:
Always consider to put "))" in the queue to process since original one "())" is not a valid string.
One more test to remove one char - case study 2
")()"
First, it is not valid parentheses string. So at least one parenthese should be removed.
Go over each index position of string ")()", remove the char,
First one is index = 0; "()" is valid one, so "()" is added to output;
Second one is index = 1; "))" is not valid, but output list is not empty, continue;
Third one is index = 2; ")(" is not valid one.
It is important to go over a few simple test cases to understand how BFS works, and then it is time to think about how to prune the algorithm and make it more efficient.
Here are those two important steps:
First, push Tuple<string, int>("())",0) into queue;
and then go over each index position from "())", remove each char, see if it is valid or not.
Case study 3: Remove two parentheses
String "())(()", how to find the valid string "()()" to remove two parentheses?
The above test case is so helpful for me to understand BFS, first remove one parenthese, all those substrings are not valid string, which should be queued for next removal of one more parenthese.
Work on the iteration. I will add more explanation for this test case.
"))(()", 0
"()(()", 1
"()(()", 2
"())()", 3
"())()", 4
"())((", 5
From the above four test cases, "())()", 4 should be same as "())()", 3. So it is not needed to be repeated.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _301_remove_invalid_parentheses___2020
{
class Program
{
static void Main(string[] args)
{
var result3 = RemoveInvalidParentheses("())(()");
}
public static IList<string> RemoveInvalidParentheses(string s)
{
var set = new HashSet<string>();
if (IsValidParentheses(s))
{
set.Add(s);
return set.ToList();
}
var queue = new Queue<Tuple<string, int>>();
queue.Enqueue(new Tuple<string, int>(s, 0));
while (queue.Count > 0)
{
var current = queue.Dequeue();
var search = current.Item1;
var start = current.Item2;
for (int index = start; index < search.Length; ++index)
{
var visit = search[index];
bool isParenthese = visit == '(' || visit == ')';
if (!isParenthese)
{
continue;
}
var skipCurrent = search.Remove(index, 1);
if (IsValidParentheses(skipCurrent))
{
set.Add(skipCurrent);
continue;
}
if (set.Count == 0)
{
queue.Enqueue(new Tuple<string, int>(skipCurrent, index));
}
}
}
return set.ToList();
}
public static bool IsValidParentheses(String s)
{
int count = 0;
for (int i = 0; i < s.Length; ++i)
{
var visit = s[i];
var isOpen = visit == '(';
var isClose = visit == ')';
if (isOpen)
{
++count;
}
if (isClose)
{
bool noOpenToMatch = count <= 0;
if (noOpenToMatch)
{
return false;
}
count--;
}
}
return count == 0;
}
}
}
