C# BFS approach without pruning practice in June 2020
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.
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.
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.
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
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.
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.
")()"
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.
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.
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
"()(()", 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 reuslt = RemoveInvalidParentheses("()"); // original one valid or not - step 1
//var result2 = RemoveInvalidParentheses("())"); // need to remove one parentheses - step 2
var result3 = RemoveInvalidParentheses("())(()");
}
/// <summary>
/// code review on June 22, 2020
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static IList<string> RemoveInvalidParentheses(string s)
{
var set = new HashSet<string>();
// return if it is valid
if (IsValidParentheses(s))
{
set.Add(s);
return set.ToList();
}
// How to design a queue - BFS to solve the problem?
// think about a string to remove two parentheses, "())(()",
// those strings with one char removed should be enqueued for next removal of char
var queue = new Queue<Tuple<string, int>>();
//The 2-Tuple is (string, startIndex)
queue.Enqueue(new Tuple<string, int>(s, 0));
while (queue.Count > 0)
{
var current = queue.Dequeue();
var search = current.Item1;
var start = current.Item2;
// Start from last removal position
for (int index = start; index < search.Length; ++index)
{
var visit = search[index];
//Not parentheses
bool isParenthese = visit == '(' || visit == ')';
if (!isParenthese)
{
continue;
}
// remove visit char from the string
//var skipCurrent = search.Substring(0, index) + search.Substring(index + 1);
var skipCurrent = search.Remove(index, 1);
//Check the string is valid
if (IsValidParentheses(skipCurrent))
{
set.Add(skipCurrent);
continue; // continue to iterate all index positions
}
// think about test case: ())(() -> minimum is to remove two parentheses
// Strings with one char removed are not working, then BFS goes to second remove
// Four strings will be in the queue.
// "))(()", 0
// "()(()", 1
// "()(()", 2
// "())()", 3
// "())()", 4
// "())((", 5
if (set.Count == 0)
{
queue.Enqueue(new Tuple<string, int>(skipCurrent, index));
}
}
}
return set.ToList();
}
/// <summary>
/// test case:
/// "()","(())", "()()" true
/// ")(","())" false
/// Time complexity: O(N)
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
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;
}
}
}