## Given a string of parentheses, determine if its valid (well-formed)

0 / 207

Problem Statement

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: “()”

Output: true

Example 2:

Input: “()[]{}”

Output: true

Example 3:

Input: “(]”

Output: false

Example 4:

Input: “([)]”

Output: false

Example 5:

Input: “{[]}”

Output: true

Javascript solution below

<script>

/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
var stack = [], element;
var parenType1 = 0, parenType2 = 0, parenType3 = 0;

if (s.length === 1) // edge case if string has only 1 character
return false;

for (var i = 0; i < s.length; i++) {
switch(s[i]) {
case '(':
stack.push(s[i]);
parenType1++;
break;

case ')':
element = stack.pop();
if (element !== '(')
return false;
parenType1--;
break;

case '{':
stack.push(s[i]);
parenType2++;
break;

case '}':
element = stack.pop();
if (element !== '{')
return false;
parenType2--;
break;

case '[':
stack.push(s[i]);
parenType3++;
break;

case ']':
element = stack.pop();
if (element !== '[')
return false;
parenType3--;
break;
}
}

if (parenType1 > 0 || parenType2 > 0 || parenType3 > 0)
return false;

return true;
};

document.write('Input string "()" is balanced = '+isValid("()")+'<br/>');
document.write('Input string "()[]{}" is balanced = '+isValid("()[]{}")+'<br/>');
document.write('Input string "(]" is balanced = '+isValid("(]")+'<br/>');
document.write('Input string "([)]" is balanced = '+isValid("([)]")+'<br/>');
document.write('Input string "{[]}" isĀ balancedĀ = '+isValid("{[]}")+'<br/>');

</script>

Explanation:

We use a stack/array to keep track of the parentheses when they are encountered along with count of give 3 types of parentheses “{}”, “()” and “[]”

• Iterate through the input string, do a switch case on each of the string characters
• For all opening parentheses, push it on the stack top and increment the corresponding counter for that parentheses type by 1
• For all closing parentheses in the string, pop the stack top and compare if it matches it’s corresponding opening parentheses, if not, return false (invalid or unbalanced parentheses). If a match is found, decrement the corresponding parentheses type counter by 1
• Repeat the previous three steps till the end of the string.
• If after processing the entire string, either of the parentheses type counter aren’t zero, return false which indicates that the string isn’t balanced or well-formed.

Time and space complexity

The time and space complexity for the above algorithm is O(N) as it uses one pass and constant space (array of N characters at max).