Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Example(Taken from leetcode):
Input: "()())()" Output: ["()()()", "(())()"]
Approach: It looks like a backtracking problem(removing 1,2,3....n parenthesis and check if they are valid strings or not).
We can use BFS to optimize it. We can say str1 and str2 are connected if removing one parentheses from str1 forms str2. If we form a graph in this way and while traversing (BFS), at a particular level we find that a valid string is found then we add it to our result and also now we know that we don't need to move to next level as we want to remove minimum number of parenthesis to make string valid.
Implementation in C#:
public static IList<string> RemoveInvalidParentheses(string s)
{
if (string.IsNullOrWhiteSpace(s))
{
return new List<string>();
}
List<string> result = new List<string>();
// BFS
HashSet<string> visited = new HashSet<string>();
Queue<string> queue = new Queue<string>();
queue.Enqueue(s);
visited.Add(s);
// If we find valid string, we don't need to go to next level.
bool goToNextLevel = true;
while(queue.Count > 0)
{
s = queue.Dequeue();
if (IsStringContainsValidParentheses(s))
{
result.Add(s);
goToNextLevel = false;
}
if (!goToNextLevel)
{
continue;
}
for (int i = 0; i < s.Length; ++i)
{
if (!IsParentheses(s[i]))
{
continue;
}
string subStr = s.Substring(0, i) + s.Substring(i + 1);
if (!visited.Contains(subStr))
{
queue.Enqueue(subStr);
visited.Add(subStr);
}
}
}
return result;
}
private static bool IsParentheses(char ch)
{
return ch == '(' || ch == ')';
}
private static bool IsStringContainsValidParentheses(string s)
{
int countParentheses = 0;
foreach(char ch in s)
{
if (ch == '(')
{
++countParentheses;
}
else if (ch == ')')
{
--countParentheses;
}
if (countParentheses < 0)
{
return false;
}
}
return countParentheses == 0;
}
Complexity: O(N * 2 ^ N)
No comments:
Post a Comment