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

0 / 342
Balanced parentheses
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).      

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Tags :

Related Posts