Created
February 17, 2018 22:33
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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