MySolution
public class MissingParentheses { int missingNumber; public int countCorrections(String str){ int leftCnt = 0; for(int i=0; i<str.length(); i++){ if(str.charAt(i) == '('){ leftCnt++; }else{ if(leftCnt <=0){ missingNumber++; }else{ leftCnt; } } } return leftCnt + missingNumber; } }
Problem Statement


Given a string of parentheses, you must turn it into a well formed
string by inserting as few parentheses as possible, at any
position (you cannot delete or change any of the existing
parentheses).
A well formed string of parentheses is defined by the following
rules:

The empty string is well formed.

If s is a well formed string, (s) is a well formed string.

If s and t are well formed strings, their concatenation st is a
well formed string.
As examples, "(()())", "" and "(())()" are well formed strings and
"())(", "()(" and ")" are malformed strings.
Given a String par of parentheses, return the minimum
number of parentheses that need to be inserted to make it into a
well formed string.

Definition


Class:

MissingParentheses

Method:

countCorrections

Parameters:

String

Returns:

int

Method signature:

int countCorrections(String par)

(be sure your method is public)


Limits


Time limit (s):

2.000

Memory limit (MB):

64


Constraints



par will contain between 1 and 50 characters, inclusive.



Each character of par will be an opening or closing
parenthesis, i.e., '(' or ')'.

Examples

0)




Returns: 2

The string below is a possible well formed string you
can get to by inserting the two closing parentheses
marked.
(())(())
^ ^



1)




Returns: 1

You can fix the string by inserting a single closing
parenthesis at the end.



2)




Returns: 0

The input string is well formed, so no insertion is
needed.



3)



"())(())((()))))()((())))()())())())()()()"


Returns: 7



This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Comments
Post a Comment