CorrectingParenthesization
SRM 301 · 2006-05-09 · by soul-net
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
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 '}'.
"([{}])()[]{}"
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 "(){}[]".
"" Returns: 0
"][" Returns: 2
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CorrectingParenthesization with a public method int getMinErrors(string s) · 122 test cases · 2 s / 256 MB per case