Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 17, 2018 22:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/925dfc01fe38d273015da97ba6dbae11 to your computer and use it in GitHub Desktop.
Save jianminchen/925dfc01fe38d273015da97ba6dbae11 to your computer and use it in GitHub Desktop.
Write step 1 algorithm - remove invalid parentheses - simplify the problem, break into two steps, first remove unmatched close bracket first
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FindMinimumParentheses
{
/// <summary>
/// Step 1 algorithm of mock interview
/// remove invalid brackets from the input string
/// - take two steps, first remove unmatched close bracket
/// - reverse the string, and then redefine the open bracket as ')',
/// remove unmatched close bracket
/// - reverse the string back to normal order
/// </summary>
class Program
{
static void Main(string[] args)
{
var result = GetMinimumRequireParentheses("(())"); // (()) - correct
var resutl2 = GetMinimumRequireParentheses(")))()"); // (() - wrong
var result3 = GetMinimumRequireParentheses("(())"); // ()) - wrong
var result4 = GetMinimumRequireParentheses("((())"); // ()) - wrong
var result5 = GetMinimumRequireParentheses("((()))"); // (())) - wrong
}
public static string GetMinimumRequireParentheses(string text)
{
var leftToRight = RemoveUnmatchedCloseBracket(text, '(');
var reversed = reverseString(leftToRight);
var second = RemoveUnmatchedCloseBracket(reversed, ')');
return reverseString(second);
}
private static string reverseString(string s)
{
var array = s.ToCharArray();
Array.Reverse(array);
return new string(array);
}
public static string RemoveUnmatchedCloseBracket(string text, char openSign)
{
if(text == null || text.Length == 0)
return "";
var length = text.Length;
int openBracket = 0;
var removedUnmatchedClosed = new StringBuilder();
for(int index = 0; index < length; index++)
{
var current = text[index];
var isOpen = current == openSign;
if(isOpen)
{
openBracket++;
removedUnmatchedClosed.Append(current);
}
else
{
if(openBracket > 0)
{
openBracket--;
removedUnmatchedClosed.Append(current);
}
}
}
return removedUnmatchedClosed.ToString();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment