TopCoder problem "CorrectingParenthesization" used in SRM 301 (Division II Level Three)

Problem Statement

Given a string of parentheses, we must turn it into a well formed string by changing as few characters as possible (we cannot delete or insert characters).

There are 3 kinds of parentheses: regular (), brackets [] and curly brackets {}. Each pair has an opening ('(', '[' and '{' respectively) and a closing (')', ']' and '}') character.

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), [s] and {s} are well formed strings.
If s and t are well formed strings, the concatenation st is a well formed string.

As examples, "([{}])", "" and "(){}[]" are well formed strings and "([}]", "([)]" and "{" are malformed strings.

Given a String s of parentheses, return the minimum number of characters that need to be changed to make it into a well formed string.

Definition

Class:	CorrectingParenthesization
Method:	getMinErrors
Parameters:	String
Returns:	int
Method signature:	int getMinErrors(String s)
(be sure your method is public)

Notes

Changing a character is selecting one position in the string and changing the character in that position to any other parentheses character.

Constraints

s will have between 0 and 50 characters, inclusive.

s will have an even number of characters.

Each character of s will be '(', '[', '{', ')', ']' or '}'.

Examples

"([{}])()[]{}"

Returns: 0

This is already well formed.

"([)]"

Returns: 2

With two changes you can get "([])" (there are other ways with the same number of changes).

"([{}[]"

Returns: 1

Simply changing the second character will give you "(){}[]".

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6221

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9822&pm=6221

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Dynamic Programming, Recursion, String Manipulation